Pub crawl | cho.sh

Problem

Al has just arrived in Dublin. He is going to spend his cash on the famous Dublin activity, the pub crawl. The goal is to drink a pint of Guinness in as many different pubs as possible, never visiting the same pub twice. There are $n$ pubs in Dublin.

Al gets drunk very fast, so he sees pubs as points on a plane, and his path from one pub to the next as a straight line connecting those two points. The real walk may run along several streets, around buildings, or in circles while he looks for the next pub. Al does not care about any of that. The only thing he cares about is that every turn he makes is a left turn. For every three consecutive pubs on his route, the third one must lie in the left half plane with respect to the directed line from the first pub to the second. Builders in Dublin enjoy the pub crawl too, so they never built three or more pubs on one straight line.

Find how many pubs Al can visit and plan the route for him.

Input

The first line contains an integer $n$ , the number of pubs. ( $1 \le n \le 5000$ )

Each of the next $n$ lines contains two integers $x$ and $y$ , the coordinates of one pub. ( $-10^9 \le x, y \le 10^9$ )

Different pubs are located at different points.

Output

Print on the first line the maximum number of pubs $m$ that Al can visit. On the second line print $m$ pub indices in the order Al visits them, separated by single spaces. Pubs are numbered from 1 to $n$ in the order they appear in the input.

Several routes can satisfy the condition, so only the route fixed by the following rule is accepted.

The route starts at the pub with the smallest $y$ coordinate. If several pubs share that $y$ coordinate, it starts at the one among them with the smallest $x$ coordinate.
To pick the next pub from the current one, take the unvisited pub $q$ such that every other unvisited pub lies strictly to the left of the directed line from the current pub to $q$ . Because no three pubs lie on one straight line, exactly one such $q$ exists at every step. When one unvisited pub is left, that pub is the choice.