만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사과

시간 제한5초메모리 제한512 MB

요약
N명이 각각 사과를 들고 일정한 속도로 움직일 때, 어떤 시각 t >= 0에 무한한 속도의 직선 총알 한 발로 관통할 수 있는 사과의 최대 개수를 구한다.
난이도

어려움10점 중 8점

유형
기하, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

어느 곳에 총의 명중률에 자신이 있는 사냥꾼이 있었습니다. 사냥꾼은 어느 날, "윌리엄 텔이라는 스위스 사람이 아들의 머리 위에 사과를 올려놓고 멀리서 화살로 쏘아 떨어뜨린 묘기로 유명해졌다"는 이야기를 들었습니다. 그 이야기를 듣고 "내가 더 대단하다!!"라고 생각한 사냥꾼은 움직이는 사람 위에 사과를 올려놓고 쏘아 맞히는 묘기를 생각해냈습니다.

사냥꾼은 광장에 NN 명의 사람을 모으고, 각 사람의 위에 사과를 올려놓았습니다. ii 번째 사람은 시각 t=0t=0 일 때 좌표 (xi,yi)(x_i, y_i) 에 있습니다. 그곳에서 속도 벡터 (ui,vi)(u_i, v_i) 에 따라 걷습니다. 즉, 시각 t≥0t \ge 0 일 때, ii 번째 사람은 좌표 (xi+t×ui,yi+t×vi)(x_i + t \times u_i, y_i + t \times v_i) 에 있습니다. 여기서 사람들은 충분히 작으므로, 같은 좌표에 여러 사람이 있거나 같은 좌표에서 서로 스쳐 지나갈 수 있다고 가정합니다.

사냥꾼은 사람들을 감탄시키기 위해, 한 발의 탄환으로 가능한 한 많은 사과를 쏘아 떨어뜨리기로 했습니다. 사냥꾼은 t≥0t \ge 0 인 임의의 시각에, 임의의 좌표에서 임의의 방향으로 탄환을 발사할 수 있습니다. 발사된 탄환은 무한한 속도로 직선 궤도를 이동하며, 사과에 맞으면 관통하여 이동합니다. 탄환을 한 발만 쏠 때, 최대 몇 개의 사과를 떨어뜨릴 수 있는지 계산하세요.

입력

입력은 다음 형식으로 주어집니다.

NN

x1x_1 y1y_1 u1u_1 v1v_1

......

xNx_N yNy_N uNu_N vNv_N

출력

떨어뜨릴 수 있는 사과의 최대 개수를 한 줄에 출력합니다.

제한

  • 1≤N≤2001 \le N \le 200
  • 0≤∣xi∣,∣yi∣≤100 \le |x_i|, |y_i| \le 10
  • 0≤∣ui∣,∣vi∣≤30 \le |u_i|, |v_i| \le 3
  • 입력값은 모두 정수입니다.

예제3

  1. 예제 1

    입력
    5
    0 0 0 0
    1 0 -1 1
    -1 0 1 -1
    1 1 -1 1
    -1 -1 1 -1
    
    예상 출력
    5
    
  2. 예제 2

    입력
    5
    0 0 0 0
    1 0 1 0
    -1 0 -1 0
    1 1 1 1
    -1 -1 -1 -1
    
    예상 출력
    3  
    
  3. 예제 3

    입력
    15
    -10 9 2 1
    2 10 0 -1
    -10 -4 0 -3
    -2 8 0 -1
    0 -10 -1 -2
    -8 5 0 -1
    -7 -8 -3 1
    10 -6 -2 -3
    9 -6 1 0
    10 -5 3 1
    10 1 0 -3
    -4 7 0 -1
    10 -9 2 2
    2 -5 -1 1
    9 -10 3 1
    
    예상 출력
    5