Nexus-6 revolt P52741


Statement
 

pdf   zip

html

[r]

Year 2019. Nexus-6, the last generation of replicants, have just revolted. They are leaded by Roy Batty, a combat model with the intellect of a genius. Roy is now alone, surrounded by human enemy forces near the Tannhauser Gates. Fortunately for it (replicants are machines, so they are neither “he” nor “she”), those humans are not Blade Runners, but just plain policemen. Therefore, Roy will have no difficulties eliminating them all with its laser gun.

Roy is located at (0, 0). Initially, Roy’s laser gun is beaming towards the north, that is, in the (0, 1) direction. When Roy turns its laser gun (right or left), every human in front of it disappears immediately. Roy wants to minimize its effort (measured as the number of degrees turned) while destroying all those insignificant humans. Help it!

Input

Input is all integer numbers with absolute value at most 104, and consists of several cases. Every case begins with the number of humans n ≥ 1, followed by n different positions (x, y). No given position is (0, 0). A special case with n = 0 ends the input.

Output

For every case, print with two digits after the decimal point the minimum number of degrees that Roy must turn to eliminate all human forces. The input cases have no precision issues, and the result will always be strictly positive.

Public test cases
  • Input

    1   3 3
    2   1 -1   2 1
    3   -1 -2   -1 0   -4 0
    3   -1 1   0 1   1 1
    0
    

    Output

    45.00
    135.00
    153.43
    135.00
    
  • Information
    Author
    Marçal Garolera
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Semifinal
    Date
    2008-06-28