문제1271--KoreaTech 최고의 사격 선수

1271: KoreaTech 최고의 사격 선수

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

대승이와 종욱이는 Koreatech 최고의 사격 선수를 가려내기 위해 대회를 기획하였습니다. 기획 결과, 이번 사격 대회에서는 다음과 같은 새로운 규칙들을 적용하기로 하였습니다.

  1. 오직 1회에 한해서 총을 발사할 수 있습니다.
  2. 2차원의(x, y 축의)평야에서 대회가 진행되며, 평야에는 일정 지점 마다 풍선들이 설치되어 있습니다.
  3. 같은 지점에 여러 개의 풍선이 설치되어 있을 수도 있습니다. 
  4. 총은 아무데서나 쏠 수 있습니다.
위와 같은 조건이 주어졌을 때, 오직 한번의 발사만으로 가장 많은 풍선을 터트렸을 때의 개수를 구해주세요. 단, 발사된 총알은 직선 운동을 하며, 운동에너지의 소실은 없다고 가정합니다.

주어진 풍선의 좌표들이 아래와 같으면 사격 경기장의 모습은 아래와 같습니다.
(-3 -3), (2 3), (-2 -2), (5 7), (-1 -1)




입력 설명

첫 줄에는 풍선의 개수 N (1 ≤ N ≤ 300)이 주어집니다. 그 다음 N개 줄에 걸쳐 풍선의 좌표가 X (−104 ≤ X ≤ 104)와 Y (−104 ≤ Y ≤ 104)가 주어집니다.

출력 설명

한번의 발사만으로 가장 많은 풍선을 터트릴수 있는 최대 숫자를 출력합니다.

입력 예시 Copy

5
-3 -3
2 3
-2 -2
5 7
-1 -1

출력 예시 Copy

3

출처/분류