Never trust Ivan (2) P46204


Statement
 

pdf   zip

thehtml

Given n points on the plane p1 … pn no three of which are collinear, find a permutation of the points pi1 … pin such that the n segments (pi1, pi2), (pi2, pi3), …, (pin−1, pin), (pin, pi1) form a non-degenerate polygon, that is, one that does not cross itself.

Input

Input consists of several cases, each one with n followed by n points with integer coordinates not larger than 107 in absolute value. Assume 3 ≤ n ≤ 104, and that no three given points are collinear.

Output

For every case, print a correct polygon constructed from the n points. If there is more than one solution, print any of them. If there is no solution, print “Ivan is a troll”.

Public test cases

  • Input

    4  0 0  1 1  0 1  1 0
3  0 0  10 10  15 20
5  -1 -1  -3 -3  -1 1  1 -2  -2 0
4  0 0  -1 1  0 -1  1 -2
7  -9 -4  0 -5  2 3  1 7  0 0  5 -5  1 4

    Output

    1 4 2 3
1 2 3
2 4 1 3 5
3 4 1 2
1 2 6 5 3 7 4
    • Information
    Author
    Ivan Geffner
    Language
    English
    Official solutions
    C++
    User solutions
    C++