G - Worst Picture Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600

問題文

3 次元空間に N 人の人がいます。i 番目の人は座標 (X_i,Y_i,Z_i) にいます。
人のいる座標は相異なり、全ての iX_i>0 です。

あなたは x<0 であるような点 p=(x,y,z) を選び、そこから 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 番目の人は写真に写りません。


入力例 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) から写真を撮ると、写る人数は 4 人になります。

Score : 600 points

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.