読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

幾何

LiveArchive 6503 : Golf Field

問題文 : https://icpcarchive.ecs.baylor.edu/external/65/6503.pdf問題概要 : 2次元平面上にn個の点がある. ( 4 この中から異なる4点を選び凸包を作る. 得られる凸包の面積の最大値を求めよ.解法 : 凸包 + キャリパー法 + 三分探索以下の問題の完全上位…

AOJ 2073 : The Phantom

問題リンク : The Phantom | Aizu Online Judge問題概要 : 2次元平面上に2枚の鏡と幽霊がいる 鏡と幽霊はそれぞれ線分と点として表される 鏡に映る幽霊の数を出力せよ ただし、その数が100を超える場合は"TOO MANY"と出力せよ解法 :よくあるビームと鏡の反…

AOJ 2464 : Magic Walls

問題リンク : Magic Walls | Aizu Online Judge問題概要 : 4個以上1500個以下の2次元座標上の点が与えられる その中から異なる4点を選びlそこから作られる四角形の面積の最大値を求めよ 任意の異なる3点が直線上に並ぶことはないし、 任意の異なる2点が同…

AOJ 2167 : Find the Point

問題リンク : Find the Point | Aizu Online Judge問題概要 : n本の直線が与えられる それら全ての直線への最短距離が等しい点を見つけよ そのような点が複数ある場合は "Many" と出力し、 1つも存在しない場合は "None" と出力せよ解法 :まず、直線が2本だ…

AOJ 0253 : Ant Nest

問題リンク : Ant Nest | Aizu Online Judge問題概要 : 略解法 : 重心求めてくるくるしながら二分探索して計算するまず最初に、連続した3点以上が平行であるようなものが入力として与えられるので、それらを圧縮して1つの線分にする各辺について、そこをケ…

AOJ 2246 : Alice and Bomb

問題リンク : Alice and Bomb | Aizu Online Judge問題概要: 建物、人、爆弾があり、建物は2次元平面上の多角形として、人と爆弾は2次元平面上の点として与えられる 爆弾は爆発すると全方位に爆風が広がる 建物に爆風が当たるとそこでそこの爆風は遮られる…

Codeforces 498A : Crazy Town

問題リンク : Problem - 498A - Codeforces問題概要 : 2次元平面上の異なる2点とn本の直線が与えられる 2つの直線が同一であることはないし、2点が線分上に存在することもない 2点のうち片方からもう片方へ移動する際にまたがなければならない線分の数…

AOJ 2537 : Billiard

問題リンク : Billiard | Aizu Online Judge問題概要 : (0,0)が左下で(w,h)が右上となるような長方形があり、 その内部にn個の半径rの円がおいてある それらは1から順番に番号が割り振られている 1番のボールを(vx,vy)方向に打つ 打たれたボールは10000秒間…

AOJ 2121 : Castle Wall

問題リンク : Castle Wall | Aizu Online Judge問題概要 : 単純多角形が与えられる 自分はこの多角形の2頂点を選んで新たに辺を付け加えることができる これを0回以上行うことができるのだが、その際に追加した辺の長さの総和がr以下でなければならない この…

AOJ 1288 : Digits on the Floor

問題リンク : Digits on the Floor | Aizu Online Judge問題概要 : 線分の情報が与えられる 0から9の数字がそれぞれ何回現れるか数えよ 細かい制約は略解法 : 最初にunion-findで繋がっている線分をまとめる 各まとまりについて、 各線分の別の線分と交差す…

UVa 12509 : Tin Cutter II

問題リンク : http://uva.onlinejudge.org/external/125/12509.html問題概要: n本の線分が与えられる 線分はx軸かy軸に平行である 外側から到達可能な線分の部分の長さの総和を求めたい解法 : 線分アレンジメント + 座標圧縮 + DFS 線分をアレンジメントし…

AOJ 1047 : Crop Circle

問題リンク : Crop Circle | Aizu Online Judge問題概要 : n個の円の中心点の座標と半径が与えられる 円周上で他のどの円にも囲まれていないような部分の長さの総和を求めよ解法 : 各円について、他の円との交点で細分化する 例えば円0については以下通りに…

AOJ 2097 : Triangles

問題リンク:Triangles | Aizu Online Judge問題概要: 1辺の長さが1の正三角形をn個、任意の点を中心として 360/n 度間隔で置いていく この時n個の正三角形が覆う面積はどのくらいか?解法: 正多角形から余計な部分を引いて面積を出した上の図の黒い矢印…

AOJ 1254 : Color the Map

問題リンク:Color the Map | Aizu Online Judge問題概要: 10個以下の国の情報が多角形として与えられる それらの国に色を塗っていきたいのだが、隣接する国同士は異なる色で塗りたい 同じ国であるならば同じ色で塗らなければならない 最低何色必要か解法:…

UVa 10577 : Bounding box

問題リンク : http://uva.onlinejudge.org/external/105/10577.html問題概要 : 正多角形のうち3点だけが与えられる その3点から本来の正多角形を復元し、その正多角形を囲むようなx軸とy軸に平行な長方形の面積の最少値を求めよ解法 : 正n角形の中心点が分…

UVa 10445 : Make Polygon

問題リンク:http://uva.onlinejudge.org/external/104/10445.html問題概要: 多角形が与えられる その多角形の連続する3点からなる角度の最大と最小を求めよ解法: 全ての角度をみてその中の最大と最小を求める 入力は時計回りで与えられるのか反時計回りで…

UVa 10382 : Watering Grass

問題リンク:http://uva.onlinejudge.org/external/103/10382.html問題概要: 略解法: 円と長方形が交差する場所のx座標を計算で求める 円の中心点の座標を(x,y)、円の半径をrとすると 円と長方形が交差する場所のx座標(以下 nx)は以下の通り nx = +sqrt(r*…

UVa 10136 : Chocolate Chip Cookies

問題リンク:http://uva.onlinejudge.org/external/101/10136.html問題概要: 複数の点が与えられる 好きな場所に直径5cmの円を置いたときにその円の内部に入る点の数を最大化せよ解法: AOJ1132やAOJ0090と同じ問題 円の半径が2.5になっただけある2点を決…

AOJ 1279 : Geometric Map

問題リンク : Geometric Map | Aizu Online Judge問題概要: n本の線分が与えられる (n 線分は必ず1本以上の他の線分と端点で交差している 線分の両端が別の線分の端点と交差しているならばそれは道である 線分の片方だけが別の線分の端点と交差しているな…

AOJ 1171 : Laser Beam Reflections

問題リンク : Laser Beam Reflections | Aizu Online Judge解法: レーザービームを打つ方向を360度ちょっとずつずらしながらシュミレーションした レーザービームを打つ方向さえ決めてしまえばそこからゴールまで到達できるかどうかは一意に定まるので判…

AOJ 1301 : Malfatti Circles

問題リンク:Malfatti Circles | Aizu Online Judge問題概要: 略解法: 3つの円の半径はそれぞれ以下のサイトにのっている式で求めることが可能http://forumgeom.fau.edu/FG2003volume3/FG200308.pdf2つの円の半径を2分探索をして求める方法もあるみたい2…