B - Make Many Triangles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

二次元平面上に相異なる N 個の点があります。 i 番目の点の座標は (x_i,y_i) です。

これらの点のいずれかを頂点とする（非退化な）三角形をたくさん作りたいです。ただし、同じ点を複数の三角形の頂点として用いることはできません。

最大で何個の三角形が作れるか求めてください。

非退化な三角形とは 非退化な三角形とは、 3 つの頂点が同一直線上に並ばない三角形のことを指します。

制約

  • 3 \leq N \leq 300
  • -10^9 \leq x_i,y_i \leq 10^9
  • i \neq j ならば (x_i,y_i) \neq (x_j,y_j)
  • 入力される値はすべて整数

入力

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

N
x_1 y_1
x_2 y_2
\vdots
x_{N} y_{N}

出力

答えを出力せよ。

入力例 1

7
0 0
1 1
0 3
5 2
3 4
2 0
2 2

出力例 1

2

例えば 1,3,6 番目の点からなる三角形と 2,4,5 番目の点からなる三角形を考えると、三角形を 2 つ作ることができます。

同じ点を複数の三角形の頂点として用いることはできませんが、三角形が共通部分を持っても構いません。

入力例 2

3
0 0
0 1000000000
0 -1000000000

出力例 2

0

Score: 500 points

Problem Statement

There are N distinct points on a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

We want to create as many (non-degenerate) triangles as possible using these points as the vertices. Here, the same point cannot be used as a vertex of multiple triangles.

Find the maximum number of triangles that can be created.

What is a non-degenerate triangle? A non-degenerate triangle is a triangle whose three vertices are not collinear.

Constraints

  • 3 \leq N \leq 300
  • -10^9 \leq x_i,y_i \leq 10^9
  • If i \neq j, then (x_i,y_i) \neq (x_j,y_j)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
\vdots
x_{N} y_{N}

Output

Print the answer.

Sample Input 1

7
0 0
1 1
0 3
5 2
3 4
2 0
2 2

Sample Output 1

2

For example, if we create a triangle from the first, third, and sixth points and another from the second, fourth, and fifth points, we can create two triangles.

The same point cannot be used as a vertex for multiple triangles, but the triangles may have overlapping areas.

Sample Input 2

3
0 0
0 1000000000
0 -1000000000

Sample Output 2

0