← 返回题目列表

AtCoder · abc301_g

G. 最差图片

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 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) 是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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),它将显示四个人。