srupのメモ帳

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

幾何

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が存在するかどうかを求める問題。 解法 点対称のような図形になればいい。なんて言えばいいかわからないけど、角張った円のような。(重心関して点対称であれ…