103016: [Atcoder]ABC301 G - Worst Picture

Problem Statement

There are $N$ people in a three-dimensional space. The $i$-th person is at the coordinates $(X_i,Y_i,Z_i)$.
All people are at different coordinates, and we have $X_i>0$ for every $i$.

You will choose a point $p=(x,y,z)$ such that $x<0$, and take a photo in the positive $x$-direction.

If the point $p$ and the positions $A, B$ of two people are on the same line in the order $p,A,B$, then the person at $B$ will not be in the photo. There are no other potential obstacles.

Find the number of people in the photo when $p$ is chosen to minimize this number.

Constraints

• $1 \leq N \leq 50$
• $0 < X_i \leq 1000$
• $-1000 \leq Y_i,Z_i \leq 1000$
• The triples $(X_i,Y_i,Z_i)$ are distinct.
• All values in the input are integers.

Input

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

$N$
$X_1$ $Y_1$ $Z_1$
$\vdots$
$X_N$ $Y_N$ $Z_N$

Output

Print the answer.

Sample Input 1

3
1 1 1
2 2 2
100 99 98

Sample Output 1

2

For instance, if you take the photo from the point $(-0.5,-0.5,-0.5)$, it will not show the second person.

Sample Input 2

8
1 1 1
1 1 -1
1 -1 1
1 -1 -1
3 2 2
3 2 -2
3 -2 2
3 -2 -2

Sample Output 2

4

If you take the photo from the point $(-1,0,0)$, it will show four people.

问题描述

在一个三维空间中有 N 个人。第 i 个人的位置坐标为 $(X_i,Y_i,Z_i)$。
所有人处于不同的坐标，并且我们有 $X_i>0$ 对于每一个 i。

你将选择一个点 $p=(x,y,z)$ 使得 $x<0$，并在正 x 方向拍照。

如果点 p 和两个人 A、B 的位置在同一直线上，顺序为 p、A、B，则位于 B 的人不会出现在照片中。 没有其他潜在的障碍物。

当选择 p 以使这个数最小时，找到照片中的人数。

限制条件

• $1 \leq N \leq 50$
• $0 < X_i \leq 1000$
• $-1000 \leq Y_i,Z_i \leq 1000$
• 三元组 $(X_i,Y_i,Z_i)$ 是不同的。
• 输入中的所有值都是整数。

输入

输入从 Standard Input 按照以下格式给出：

$N$
$X_1$ $Y_1$ $Z_1$
$\vdots$
$X_N$ $Y_N$ $Z_N$

输出

打印答案。

样例输入 1

3
1 1 1
2 2 2
100 99 98

样例输出 1

2

例如，如果你从点 $(-0.5,-0.5,-0.5)$ 拍照，它不会显示第二个人。

样例输入 2

8
1 1 1
1 1 -1
1 -1 1
1 -1 -1
3 2 2
3 2 -2
3 -2 2
3 -2 -2

样例输出 2

4

如果你从点 $(-1,0,0)$ 拍照，它将显示四个人。