Masao's new house P28198


Statement
 

pdf   zip

html

(In memory of Eoin Curran.)

During the last wild party at home, Masao was unable to host so many models, as his house was too small. Therefore, he has decided to move and start celebrating parties somewhere else. To do so, he has hired an architect to build a new house for him.

The house has a convex polygon shape. The architect, however, is a bit clumsy and messes up the map of the house. Instead of giving Masao the coordinates of the vertices of the polygon, he gives him the location of the midpoints of the sides. After thinking for a while, Masao realizes that, with that information, it is not always possible to recover the original map of the house: there might be one, zero, or even an infinity of solutions consistent with the given points. Please help Masao to recover the original information, when possible.

Input

Input consists of several cases, each one with the number of vertices 3 ≤ v ≤ 105, followed by 2v real numbers, the (x,y) coordinates of the midpoints, in counterclockwise order.

Output

For every case, print “NO SOLUTION” or “INFINITE SOLUTIONS” in case there are zero or infinite solutions, respectively. If there is exactly one solution (it will always be convex, you do not have to check it), print the vertices in counterclockwise order and one per line, with four digits after the decimal point, and followed by a line with 10 dashes. Print the vertices starting with the first vertex of the side of the first midpoint. The input cases have no precision issues.

Public test cases
  • Input

    4
    0 0    0 1
    1 1    1 0
    3
    0.2 0.5    1.2 1.5    0.2 1.5
    4
    0 0    0 1    1 1    3 3
    

    Output

    INFINITE SOLUTIONS
    -0.8000 0.5000
    1.2000 0.5000
    1.2000 2.5000
    ----------
    NO SOLUTION
    
  • Information
    Author
    Javier Gómez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la UPC - Final
    Date
    2010-09-22