Score : $600$ points

问题描述

在三维空间中有 $N$ 个人。第 $i$ 个人所在的坐标为 $(X_i, Y_i, Z_i)$。

所有人的坐标各不相同，并且对于任意的 $i$，我们有 $X_i > 0$。

你需要选择一个点 $p=(x,y,z)$，满足 $x<0$，并在正 $x$ 方向拍摄一张照片。

若点 $p$ 和两个人的位置 $A$、$B$ 按照顺序 $p,A,B$ 在同一条直线上，则位于 $B$ 的人将不会出现在照片中。除此之外没有其他可能的障碍物。

请找出当选择使得该人数最小的点 $p$ 时，照片中的人数。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 08:28:12