srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

幾何

aoj 2827 凸多角形柱工業都市

問題 問題概要 スタートからゴールまで最短距離で移動したい. 影を通れば距離には加算されない. (2017 ICPC国内模擬 E) 解法 建物とその影を考えて多角形を作り, N個の多角形どうしの距離を計算して辺を作り, ダイクストラで最短距離を計算すれば良い. 建物…

aoj 2402 Milky Way

問題 問題概要 五芒星が与えられる. スタートの星からゴールの星までの移動の最小距離を求める. 星の中は移動距離に入らない. 解法 星と星の距離は, 各星は5つの辺からなっていることから, 5つの辺ぞれぞれを総当りで調べて, その中の最小値が距離になる. こ…

aoj 1157 Roll-A-Big-Ball

問題 問題概要 ボールが通る線分とそれをじゃまするN個の直方体が与えられる. 直方体に重ならずに線分をスタートからゴールまで通ることができるボールの半径の最大値を求める. 解法 長方形と線分の距離をdとして求める半径をrとすると, d <= hのとき, r = d…

aoj 2009 Area Separation

問題 問題概要 頂点を(-100,-100)、(100,-100)、(100,100)、(-100,100) とする正方形とn個の線分が与えられる. 線分の両端は正方形の辺上にある. 線分により正方形がいくつに分割されるかを求めよ. 解法 順番に線分を書いていくことを考える. いま書く線分と…

ABC 033 D - 三角形の分類

問題 問題概要 N個の点が与えられる。3点選んで三角形を作るとき、鋭角、鈍角、直角三角形はそれぞれいくつずつできるかを求める。 解法 単純にやると、n3になってしまうため、TLE。。そこで、まず1点をきめて他の点へのベクトルを求めて、1点を原点とした偏…

yukicoder No.455 冬の大三角

問題 問題概要 省略。 解法 3点の1つを始点として、他の点までのベクトルを2つ求める。そのベクトルの外積を取り、外積の計算結果が0にならないならば、3つの点が一直線上にならないことになり、そこに点を置けば良いことになる。 ミス なし。 コード #inclu…

ABC 022 D - Big Bang

問題 問題概要 相似比を求める問題 解法 Aの座標に対して行われた操作は平行移動と回転なので、AとBは相似である。よって、相似比を求めれば、よいことなる。どこを見て相似比をみるかは多くの解法があるみたい。 一番簡単なのは、重心からの距離が最大の点…

ABC 016 D - 一刀両断

問題 問題概要 多角形を1つの直線で分断すると、いくつに分断されるかを求める問題。 解法 公式解説がわかりやすい。 分割された多角形の数 = 切っている本数+1 = (多角形と線分の交点の数 / 2) +1 = (線分と交差する多角形の辺の本数 / 2) +1 ミス 写経。…

aoj 2442 ConvexCut

問題 問題概要 与えられた図形が、点Pを通るどのような直線で切ったとしても、面積を2等分する点Pが存在するかどうかを求める問題。 解法 点対称のような図形になればいい。なんて言えばいいかわからないけど、角張った円のような。(重心関して点対称であれ…