Pulsars

On November 28, 1967, a mysterious radio source was discovered in our galaxy. What was initially thought to be the creation of extraterrestrial intelligence turned out to be due to the periodic radiation emitted by certain mysterious stars (pulsars), later recognized as neutron stars. The mapping of these stars in our galaxy began immediately, quickly providing explanations for many questions about the evolution of stars.

The mapping is done by projecting the celestial (spherical) coordinates of pulsars onto the Cartesian plane. For cosmology, it is crucial to find the convex hull that minimally encloses all pulsars located in a region of our galaxy.

The convex hull is the polygon that contains all given points in the plane, is convex, and has the smallest possible area. Convex means that each angle of the polygon is convex, and thus, the significant property holds that every line connecting two points of the original set lies entirely within the polygon. For any finite set of points, there is always a minimum convex polygon. The problem of finding the minimum convex polygon (convex hull) often appears in computer science and has many applications, as you can read at http://en.wikipedia.org/wiki/Convex_hull.

Problem

Develop a program in one of the IOI languages that takes as input the coordinates ~(X,\;Y)~ of each point in a set of pulsars on the plane and returns the vertices that constitute the minimum convex polygon enclosing all pulsars. Assume that there are no more than two pulsars on the sides of the polygon lying on the same line.

Input File

The input file named pulsars.in is a text file with the following structure: The first line contains the integer ~N\;(10 \le N \le 1.000.000)~. The next ~N~ lines each contain a pair of integers ~X~ and ~Y~ ~(0 \le X, Y \le 40.000)~, corresponding to the coordinates of each pulsar on the plane.

Output File

The output file named pulsars.out is a text file with the following structure: The first line contains the integer ~M~ ~(3 \le M \le N)~, the number of points that are vertices of the minimum convex polygon. The next ~M~ lines each contain an integer ~P~ ~(1 \le P \le N)~. The number ~P~ corresponds to the order in which the pulsar appears in the input file, whose position in the Cartesian plane is a vertex of the minimum convex polygon. These points should be given in ascending order, not necessarily in the order they appear in the convex polygon.

Notes

1. The order of appearance of the pulsars that are vertices of the minimum convex polygon must be ascending in the output file.
2. There is always a minimum convex polygon that encloses all pulsars.
3. In all test cases, the output file will be unique. That is, there will never be three points belonging to the minimum convex polygon that are collinear. Every point that lies on the sides of the minimum convex polygon is also a vertex of it.
4. There will never be two pulsars at exactly the same position.
5. No assumption can be made about the order in which the points appear in the input file. They will not necessarily be sorted.

Examples of Input - Output Files:

1st

STDIN (pulsars.in)

10
1 5
2 10
5 5
3 8
6 10
8 7
9 10
8 11
9 3
3 1

STDOUT (pulsars.out)

6
1
2
7
8
9
10

Explanation of the first example

The points provided in the input file are ~10~ and are shown in the diagram below.

The points given in the input file are marked in red, while the minimum convex polygon is depicted with blue lines. As evident, points ~1~, ~2~, ~8~, ~7~, ~9~, and ~10~ alone constitute the minimum convex polygon. Although these points appear in the polygon in the order mentioned above, they are printed in ascending order in the output file, i.e., ~1~, ~2~, ~7~, ~8~, ~9~, ~10~.

2nd

STDIN (pulsars.in)

10
1 7
9 7
1 1
9 1
2 4
8 4
6 5
6 3
4 3
4 5

STDOUT (pulsars.out)

4
1
2
3
4

Maximum execution time: 5 sec.
Maximum available memory: 64 MB.

For ~50~ % of the test cases, ~10 \le N \le 1000~.