B - Make Many Triangles

Contest Duration: 2024-03-10(Sun) 12:00 - 2024-03-10(Sun) 14:00 (local time) (120 minutes) Back to Home

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}$

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

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

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

入力例 2Copy

Copy

3
0 0
0 1000000000
0 -1000000000

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

3
0 0
0 1000000000
0 -1000000000

Sample Output 2Copy

Copy