幾何
問題リンク : Walk under a Scorching Sun | Aizu Online Judge問題概要 : いくつかのの道と建物に加え太陽がある。 道、建物、太陽はそれぞれ線分、凸多角形+高さ、点として表される。道の上にあるある点xと太陽を結ぶ直線が建物と交差するなら、 その点xは…
問題文 : https://icpcarchive.ecs.baylor.edu/external/65/6503.pdf問題概要 : ２次元平面上にn個の点がある. ( 4 この中から異なる４点を選び凸包を作る. 得られる凸包の面積の最大値を求めよ.解法 : 凸包 + キャリパー法 + 三分探索以下の問題の完全上位…
問題リンク : The Phantom | Aizu Online Judge問題概要 : 2次元平面上に２枚の鏡と幽霊がいる 鏡と幽霊はそれぞれ線分と点として表される 鏡に映る幽霊の数を出力せよ ただし、その数が100を超える場合は"TOO MANY"と出力せよ解法 :よくあるビームと鏡の反…
問題リンク : Magic Walls | Aizu Online Judge問題概要 : 4個以上1500個以下の2次元座標上の点が与えられる その中から異なる４点を選びlそこから作られる四角形の面積の最大値を求めよ 任意の異なる３点が直線上に並ぶことはないし、 任意の異なる2点が同…
問題リンク : Find the Point | Aizu Online Judge問題概要 : n本の直線が与えられる それら全ての直線への最短距離が等しい点を見つけよ そのような点が複数ある場合は "Many" と出力し、 １つも存在しない場合は "None" と出力せよ解法 :まず、直線が2本だ…
問題リンク : Ant Nest | Aizu Online Judge問題概要 : 略解法 : 重心求めてくるくるしながら二分探索して計算するまず最初に、連続した３点以上が平行であるようなものが入力として与えられるので、それらを圧縮して１つの線分にする各辺について、そこをケ…
問題リンク : Alice and Bomb | Aizu Online Judge問題概要: 建物、人、爆弾があり、建物は２次元平面上の多角形として、人と爆弾は２次元平面上の点として与えられる 爆弾は爆発すると全方位に爆風が広がる 建物に爆風が当たるとそこでそこの爆風は遮られる…
問題リンク : Problem - 498A - Codeforces問題概要 : ２次元平面上の異なる２点とn本の直線が与えられる ２つの直線が同一であることはないし、２点が線分上に存在することもない ２点のうち片方からもう片方へ移動する際にまたがなければならない線分の数…
問題リンク : Billiard | Aizu Online Judge問題概要 : (0,0)が左下で(w,h)が右上となるような長方形があり、 その内部にn個の半径rの円がおいてある それらは1から順番に番号が割り振られている 1番のボールを(vx,vy)方向に打つ 打たれたボールは10000秒間…
問題リンク : Castle Wall | Aizu Online Judge問題概要 : 単純多角形が与えられる 自分はこの多角形の2頂点を選んで新たに辺を付け加えることができる これを0回以上行うことができるのだが、その際に追加した辺の長さの総和がr以下でなければならない この…
問題リンク : Digits on the Floor | Aizu Online Judge問題概要 : 線分の情報が与えられる 0から9の数字がそれぞれ何回現れるか数えよ 細かい制約は略解法 : 最初にunion-findで繋がっている線分をまとめる 各まとまりについて、 各線分の別の線分と交差す…
問題リンク : http://uva.onlinejudge.org/external/125/12509.html問題概要： n本の線分が与えられる 線分はx軸かy軸に平行である 外側から到達可能な線分の部分の長さの総和を求めたい解法 : 線分アレンジメント + 座標圧縮 + DFS 線分をアレンジメントし…
問題リンク : Crop Circle | Aizu Online Judge問題概要 : n個の円の中心点の座標と半径が与えられる 円周上で他のどの円にも囲まれていないような部分の長さの総和を求めよ解法 : 各円について、他の円との交点で細分化する 例えば円0については以下通りに…
問題リンク：Triangles | Aizu Online Judge問題概要： 1辺の長さが１の正三角形をn個、任意の点を中心として 360/n 度間隔で置いていく この時n個の正三角形が覆う面積はどのくらいか？解法： 正多角形から余計な部分を引いて面積を出した上の図の黒い矢印…
問題リンク：Color the Map | Aizu Online Judge問題概要： 10個以下の国の情報が多角形として与えられる それらの国に色を塗っていきたいのだが、隣接する国同士は異なる色で塗りたい 同じ国であるならば同じ色で塗らなければならない 最低何色必要か解法：…
問題リンク : http://uva.onlinejudge.org/external/105/10577.html問題概要 : 正多角形のうち３点だけが与えられる その３点から本来の正多角形を復元し、その正多角形を囲むようなx軸とy軸に平行な長方形の面積の最少値を求めよ解法 : 正n角形の中心点が分…
問題リンク：http://uva.onlinejudge.org/external/104/10445.html問題概要： 多角形が与えられる その多角形の連続する3点からなる角度の最大と最小を求めよ解法： 全ての角度をみてその中の最大と最小を求める 入力は時計回りで与えられるのか反時計回りで…
問題リンク：http://uva.onlinejudge.org/external/103/10382.html問題概要： 略解法： 円と長方形が交差する場所のx座標を計算で求める 円の中心点の座標を(x,y)、円の半径をrとすると 円と長方形が交差する場所のx座標(以下 nx)は以下の通り nx = +sqrt(r*…
問題リンク：http://uva.onlinejudge.org/external/101/10136.html問題概要： 複数の点が与えられる 好きな場所に直径５cmの円を置いたときにその円の内部に入る点の数を最大化せよ解法： AOJ1132やAOJ0090と同じ問題 円の半径が2.5になっただけある2点を決…
問題リンク : Geometric Map | Aizu Online Judge問題概要： n本の線分が与えられる （n 線分は必ず１本以上の他の線分と端点で交差している 線分の両端が別の線分の端点と交差しているならばそれは道である 線分の片方だけが別の線分の端点と交差しているな…
問題リンク : Laser Beam Reflections | Aizu Online Judge解法： レーザービームを打つ方向を３６０度ちょっとずつずらしながらシュミレーションした レーザービームを打つ方向さえ決めてしまえばそこからゴールまで到達できるかどうかは一意に定まるので判…
問題リンク:Malfatti Circles | Aizu Online Judge問題概要： 略解法： ３つの円の半径はそれぞれ以下のサイトにのっている式で求めることが可能http://forumgeom.fau.edu/FG2003volume3/FG200308.pdf２つの円の半径を2分探索をして求める方法もあるみたい２…
