D - 三角形の分類 Editorial /

Time Limit: 7 sec / Memory Limit: 256 MB

問題文

2 次元平面上の N 個の点が与えられます。 i 番目の点の座標は (x_i, y_i) です。ただし、このうちのどの 3 点も同一直線上にありません。

N 点のうち 3 点を選ぶことによってこの 3 点を頂点とした三角形を作ることを考えます。三角形は全部で N * (N - 1) * (N - 2) / 6 個できます。 これらの三角形のうち、鋭角三角形の個数、直角三角形の個数、鈍角三角形の個数を求めてください。

ただし、鋭角三角形とは、3 つの角が全て 90° より小さい三角形で、直角三角形とは、ある 1 つの角が 90° である三角形で、 鈍角三角形とは、ある 1 つの角が 90° より大きい三角形のことをいいます。

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 y_1
x_2 y_2
:
x_N y_N
  • 1 行目には、点の個数を表す整数 N (3 ≦ N ≦ 2,000) が与えられる。
  • 2 行目から N 行には、点の座標に関する情報が与えられる。このうち i 行目には、整数 x_i (-10,000 ≦ x_i ≦ 10,000)、 y_i (-10,000 ≦ y_i ≦ 10,000) が空白区切りで与えられる。
  • N 個の点は全て異なる。
  • N 個の点のうち、異なる 3 点が同一直線上にあることはない。

部分点

この問題には部分点が設定されている。

  • N ≦ 100 を満たすデータセットに正解した場合、部分点として 30 点が与えられる。

出力

鋭角三角形の個数、直角三角形の個数、鈍角三角形の個数をこの順に空白区切りで 1 行に出力せよ。

出力の末尾にも改行を入れること。

入力例 1

5
1 3
2 2
3 2
4 1
4 3

出力例 1

1 2 7
  • 2 番目の点、4 番目の点、5 番目の点を選ぶと、鋭角三角形ができます。
  • 1 番目の点、4 番目の点、5 番目の点を選ぶと、直角三角形ができます。
  • 3 番目の点、4 番目の点、5 番目の点を選ぶと、直角三角形ができます。
  • その他の 7 通りの選び方では、全て鈍角三角形ができます。

入力例 2

9
2 0
1 1
3 1
1 2
5 2
0 3
4 3
2 4
4 4

出力例 2

27 14 43