3270. 切西瓜

单点时限: 2.0 sec

内存限制: 256 MB

切西瓜的时候正好切到瓜子这种事情确实是有可能的,不过很少发生,因为瓜子实在太少了。

切西瓜的时候切到很多瓜子也是有可能的,只要西瓜里面的瓜子足够多。

现在有一把平的刀(你只能用一个平面把西瓜切成两半),刀的厚度可以忽略不计;有一个西瓜,已经通过某种手段获知,西瓜内部有 $n$ 个瓜子(瓜子可以看作一个点),每个瓜子用一个三维坐标表示。西瓜足够大,保证所有的瓜子都在西瓜内。问如果用刀去切西瓜,最多能切到多少瓜子。

输入格式

第 $1$ 行一个整数 $n$。

第 $2$ 到 $n+1$ 行,每行三个整数 $x_i,y_i,z_i$,表示第 $i$ 个瓜子的坐标是 $(x_i,y_i,z_i)$。数据保证每个坐标仅会出现一次。

数据包含 $10$ 个测试文件,每个测试文件含有单个测试点。其中:

  • 测试点 $1,2,3$ 满足:$3 \leq n \leq 4$。
  • 测试点 $4,5,6,7$ 满足:$3 \leq n \leq 80$。
  • 测试点 $8,9,10$ 满足:$3 \leq n \leq 200$。

对于所有测试点,满足 $-10^9 \leq x_i,y_i,z_i \leq 10^9$。

输出格式

输出一个整数,表示最多能切到多少瓜子。

样例

Input
3
0 0 0
1 0 1
0 1 1
Output
3
Input
4
0 0 0
1 0 1
0 1 1
1 1 1
Output
3

提示

三维空间平面方程为 $Ax+By+Cz+D=0$,其中 $A,B,C,D$ 为常数。

8 人解决,31 人已尝试。

9 份提交通过,共有 106 份提交。

8.2 EMB 奖励。

创建: 3 年,1 月前.

修改: 2 年,10 月前.

最后提交: 8 月,3 周前.

来源: 2017 华东师范大学校赛

题目标签