바이트랜드 대조약

면접 대비

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

요약

수도 좌표가 주어질 때 보로노이 영역이 무한히 뻗는 왕국의 번호를 구합니다. 이는 볼록 껍질 경계 위에 있는 수도입니다.

난이도: 보통10점 중 5점
유형: 기하, 정렬
정답자: 아직 제출이 없습니다

문제

바이트랜드 대전이 끝났다. 살아남은 왕국들은 이제 세계의 모든 땅을 나눌 분할 조약을 논의하고 있다. 이 조약은 알려진 세계뿐 아니라 아직 발견되지 않았거나 사람이 살지 않는 모든 영토, 육지와 바다를 포함한다. 세계는 무한한 평면이라고 가정한다.

바이트랜드의 각 왕국에는 수도가 하나 있다. 분할 조약은 세계의 각 지점을 직선거리로 가장 가까운 수도를 가진 왕국에 배정한다. 두 개 이상의 수도와 거리가 같은 지점은 그 수도들이 속한 왕국의 경계에 놓인다. 어떤 왕국은 다른 왕국들에 둘러싸이고, 어떤 왕국은 무제한의 영토를 갖게 된다. 일부 군주가 이 조약에 반대하며 도움을 요청했다. 각 수도의 좌표가 주어졌을 때, 조약에 따라 무한한 영토를 갖게 되는 왕국을 찾아라.

입력

첫 줄에 왕국의 수 $N$ ( $2 \le N \le 10^5$ )이 주어진다. 각 왕국은 1부터 $N$ 까지의 서로 다른 정수로 구분된다. 다음 $N$ 개의 줄에는 각 왕국 수도의 좌표 $X$ 와 $Y$ ( $0 \le X, Y \le 10^4$ )가 두 정수로 주어진다. 수도는 왕국 번호의 오름차순으로 주어지며, 같은 위치에 있는 수도는 없고 각 수도의 크기는 무시할 만큼 작다.

출력

무한한 영토를 갖는 왕국의 번호를 오름차순으로, 공백으로 구분하여 한 줄에 출력한다. 그런 왕국은 적어도 하나 있음이 보장된다.

예제2

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