Garden

Time limit1sMemory limit1024 MB

Summary

Given a closed polygon fence and a viewer position, list the fence segments whose visible part has a length greater than zero.

Level: Medium6 of 10
Topics: Geometry, Brute force
Solved: No attempts yet

Problem

Onu Uno is building a fence around his farm. The fence is a closed polyline made of $N$ straight segments. Each segment starts where the previous one ends, and the last segment ends at the starting point of the first one. The segments are numbered $1 \ldots N$ in counterclockwise order. No two fence segments cross or touch, except at the shared endpoints of consecutive segments.

After the fence is finished, Onu Uno wants to look it over. Write a program that takes Onu Uno's position and finds which fence segments he can see from there. He may stand inside or outside the fence, but he cannot stand on the same line as any fence segment.

Onu Uno can see a fence segment if there is a straight line from his position to some point of that segment that does not cross or touch any other fence segment. In other words, the visible part of the segment must have a length greater than zero.

Input

The first line contains the number of fence segments $N$ ( $3 \le N \le 1\,000$ ). The second line contains two space-separated integers $X$ and $Y$ , the coordinates of Onu Uno. Each of the next $N$ lines contains two space-separated integers: on line $i + 2$ , the coordinates $X_i$ and $Y_i$ of the starting point of fence segment $i$ . All coordinates are integers with absolute value at most $10^5$ .

Output

On the first line, print one integer $M$ , the number of fence segments Onu Uno can see. On the second line, print the $M$ visible segment numbers in increasing order, separated by spaces.

Examples3

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