ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC033 D - 三角形の分類

問題
提出コード

解法

直角三角形と鈍角三角形について、それぞれ直角、鈍角な角は1つの三角形につき1つです。それ以外は全て鋭角となるので、

  • 直角三角形→直角の個数

  • 鈍角三角形→鈍角の個数

  • 鋭角三角形→N(N-1)(N-2)/6から上2つの個数を引いたもの

が答えになります。
ある一点iに注目します。その点と他の点をそれぞれ結ぶと、N-1本の辺ができます。
その中のある一本の辺を選んだ際、残りのN-2本の辺の中から選んで直角(もしくは鈍角)ができるかどうかは、その2辺のなす角が90度であるかどうか(90度以上であるかどうか)を調べればよいです。
ここで、そのなす角は、
|(注目している一本の辺と、x軸のなす角)-(新たに選んだ一本の辺と、x軸のなす角)|
となっています。この、x軸とのなす角について注目すると、この値で辺を昇順でソートしておけば、二分探索により、90度(90度以上)の角の個数をO(logN)で調べることができます。
あとは、点iについて全探索をし、全ての点について同じ方法で個数を調べると、全体でO(N^{2}logN)で解けます。

感想

この問題の想定解がなるほど~と思った記憶があったので無事解けました。