Fruit Slicer

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

요약

단위원 100개 이하가 주어질 때, 하나의 무한 직선이 접하는 경우까지 포함해 지날 수 있는 원의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 완전 탐색, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

게임 개발 과목을 듣는 John은 최근 과제로 Fruit Slicer라는 모바일 게임을 만들었다. 이 게임에서 플레이어는 터치스크린을 스와이프하여 공중으로 던져진 과일을 자른다. 하지만 더 복잡한 버전에 필요한 기하학 코드를 John이 작성하지 못했기 때문에 게임은 상당히 단순하다. 게임에서 각 슬라이스는 무한히 긴 직선이고, 모든 과일은 반지름이 1인 원 모양이다. 그림은 John의 게임의 멋진 스냅샷을 보여준다.

John은 자신의 게임을 가장 친한 친구 Sean에게 소개하고, Sean은 곧 단순한 게임에 흥미를 잃는다. 하지만 알고리즘 과목의 조교인 Sean은 게임을 숙제로 바꾸기로 한다. 그는 알고리즘 과목 학생들에게 게임의 어느 순간에서든 최선의 슬라이스를 계산하는 프로그램을 작성하라고 요청한다. 과일의 위치가 주어지면, 프로그램은 한 번의 직선 스와이프로 자를 수 있는 과일의 최대 개수를 구해야 한다.

Sean의 수업을 듣는 학생으로서, 이제 당신이 이 도전을 맞이할 차례이다.

입력

첫 번째 줄에는 정수 n (1 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 각각 과일의 x, y 좌표를 나타내는 두 개의 실수가 주어진다. 모든 좌표의 절댓값은 10⁴을 넘지 않으며, 소수점 이하 두 자리까지 정확히 주어진다. 과일은 겹칠 수 있다.

출력

한 번의 직선 스와이프로 자를 수 있는 과일의 최대 개수를 출력한다. 스와이프는 선이 과일의 내부 또는 경계와 교차하면 그 과일을 자른다.

예제3

예제 1

입력

예상 출력

예제 2
입력
```
3
-1.50 -1.00
1.50 -1.00
0.00 1.00
```
예상 출력
```
3
```
예제 3
입력
```
2
1.00 1.00
1.00 1.00
```
예상 출력
```
2
```