Description

You are given a simple polygon with $n$ vertices. For each vertex, if the line segment connecting it to the origin intersects the polygon only at this vertex, then this vertex is considered valid. Your task is to output the indices of all valid vertices.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain two positive integers not exceeding $10^6$, giving the coordinates of each vertex in order. The vertices are numbered $1,2,\ldots,n$ in the input order, and they are guaranteed to be given in either clockwise or counterclockwise order.

Output Format

The first line contains a positive integer $m$, the number of valid vertices.

The second line contains $m$ positive integers, in increasing order, giving the indices of the valid vertices.

11
7 6
4 4
3 2
1 3
9 9
13 4
8 1
6 4
9 5
8 3
11 5

3
3 4 7

Hint

Constraints: for $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$.

Translated by ChatGPT 5