가장 많은 점이 놓인 타원

시간 제한6초메모리 제한1024 MB

요약

정수 좌표의 점 N개가 주어졌을 때, 원점을 중심으로 하는 타원 (x/a)² + (y/b)² = c² 위에 함께 놓이는 점의 최대 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 기하, 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

$0$ 이 아닌 실수 $a$ , $b$ 와 실수 $c$ 에 대해 $\left(\frac{x}{a}\right)^2+\left(\frac{y}{b}\right)^2=c^2$ 을 만족하는 점 $(x, y)$ 의 집합을 원점타원이라고 한다. 주어진 $N$ 개의 점 중에서 같은 원점타원 위에 있는 점의 최대 개수를 구하시오.

입력

첫 번째 줄에 점의 개수 $N$ 이 주어진다. ( $2 \le N \le 3000$ )

다음 $N$ 개 줄에는 점의 위치 $(x, y)$ 를 나타내는 정수 $x$ , $y$ 가 공백으로 구분되어 한 줄에 하나씩 주어진다. 같은 위치에 여러 점이 있을 수 있다. ( $-10^9 \le x, y \le 10^9$ )

출력

같은 원점타원 위에 있는 점의 최대 개수를 출력한다.

예제2

예제 1
입력
```
5
0 5
1 1
3 4
5 0
1 1
```
예상 출력
```
3
```
예제 2
입력
```
4
1 1
-1 1
-1 -1
1 -1
```
예상 출력
```
4
```