1480. 2D Geometry

There are nn distinct points on a 2-dimension plane. The coordinates of the ii-th point is (xi,yi)(x_i, y_i).

If there are three points AA, BB and CC which form a triangle ABCABC with positive area, Bobo can remove them simultaneously from the plane. Also, if there are multiple triangles with positive area, Bobo can choose to remove any of them. Find the minimum number of points left on the plane if he can perform the operation for any number of times.

输入

Note from SCNUOJ admin: we don't have the official test data sets, and all tests used here are randomly generated, so expect weak tests and/or even wrong input format. Contact one of the admins if you wish to improve the tests.

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains an integer nn.

For the following nn lines, the ii-th line contains two integers xix_i and yiy_i.

  • 1n2×1051 \leq n \leq 2 \times 10^5
  • 0xi,yi1090 \leq x_i, y_i \leq 10^9 for each 1in1 \leq i \leq n
  • (xi,yi)(xj,yj)(x_i, y_i) \neq (x_j, y_j) for each 1i<jn1 \leq i < j \leq n
  • In each input, the sum of nn does not exceed 2×1052 \times 10^5.

输出

For each test case, output an integer which denotes the minimum number of points left.

样例

标准输入 复制文本
3
0 0
0 1
0 2
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2
标准输出 复制文本
3
0
0

提示

For the third test case, if Bobo chooses to remove the triangle (0,1),(1,1),(1,2){(0, 1), (1, 1), (1, 2)} first, there will be no other triangles to remove. Alternatively, Bobo can remove the triangle (0,0),(0,1),(1,1){(0, 0), (0, 1), (1, 1)} first and then (0,2),(0,3),(1,2){(0, 2), (0, 3), (1, 2)}.

来源

第六届中国大学生程序设计竞赛总决赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 10
通过 5