ABC033 D - 三角形の分類
解法
直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、
直角三角形→直角の個数
鈍角三角形→鈍角の個数
鋭角三角形→から上2つの個数を引いたもの
が答えになります。
ある一点に注目します。その点と他の点をそれぞれ結ぶと、本の辺ができます。
その中のある一本の辺を選んだ際、残りの本の辺の中から選んで直角(もしくは鈍角)ができるかどうかは、その2辺のなす角が90度であるかどうか(90度以上であるかどうか)を調べればよいです。
ここで、そのなす角は、
となっています。この、x軸とのなす角について注目すると、この値で辺を昇順でソートしておけば、二分探索により、90度(90度以上)の角の個数をで調べることができます。
あとは、点について全探索をし、全ての点について同じ方法で個数を調べると、全体でで解けます。
感想
この問題の想定解がなるほど~と思った記憶があったので無事解けました。