Great Treaty of Byteland

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given capital coordinates on a plane, list the kingdoms whose Voronoi cells are unbounded, which are the capitals on the convex hull boundary.

Level: Medium5 of 10
Topics: Geometry, Sorting
Solved: No attempts yet

Problem

The Great War of Byteland is over. The remaining kingdoms are now discussing the Division Treaty, which will split all the land in the world among them. The treaty covers not only the known world but also any territory yet to be discovered or inhabited, including land and sea. Assume the world is an infinite flat plane.

Each kingdom in Byteland has a single capital. The treaty assigns each point of the world to the kingdom whose capital is nearest in a straight line. If a point is equally close to two or more capitals, it lies on the border between their kingdoms. Some kingdoms may end up enclosed by others, while others may get unlimited territory. Some monarchs contest the treaty and ask for help. Given the coordinates of each capital, find the kingdoms that would have infinite territories under the treaty.

Input

The first line contains a single integer $N$ ( $2 \le N \le 10^5$ ), the number of kingdoms. Each kingdom is identified by a unique integer from 1 to $N$ . Each of the next $N$ lines contains two integers $X$ and $Y$ ( $0 \le X, Y \le 10^4$ ), the coordinates of a kingdom's capital. The capitals are given in increasing order of kingdom identifier, no two capitals share a location, and every capital has negligible size.

Output

Print a single line with the identifiers of the kingdoms that have infinite territories, in increasing order, separated by spaces. At least one such kingdom is guaranteed to exist.

Examples2

Example 1
Input
```
4
3 2
1 5
3 6
3 5
```
Expected output
```
1 2 3 4
```
Example 2
Input
```
6
2 1
3 3
1 4
4 5
6 3
4 3
```
Expected output
```
1 3 4 5
```