AT_abc301_g [ABC301G] Worst Picture

题目描述

在三维空间中有 $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$，使得照片中出现的人数最少，并输出这个最小人数。

输入格式

输入以如下格式从标准输入读入。

$N$
$X_1\ Y_1\ Z_1$
$X_2\ Y_2\ Z_2$
$\vdots$
$X_N\ Y_N\ Z_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 1 1
2 2 2
100 99 98

输出 #1

2

输入输出样例 #2

输入 #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 \leq N \leq 50$
• $0 < X_i \leq 1000$
• $-1000 \leq Y_i, Z_i \leq 1000$
• $(X_i, Y_i, Z_i)$ 互不相同
• 输入均为整数

样例解释 1

例如，从点 $(-0.5, -0.5, -0.5)$ 拍照时，第 $2$ 个人不会出现在照片中。

样例解释 2

从点 $(-1, 0, 0)$ 拍照时，照片中会出现 $4$ 个人。

由 ChatGPT 4.1 翻译