Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2596
The Minimal Angle

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

Peter has a sheet of paper with a polyline drawn on it. He wants to rotate this sheet to minimize the total angle of the line.

For each segment of the polyline Peter considers a directed counter-clockwise angle in range from 0 to 2*PI formed by OX axis and this segment. Peter calls the total angle of the polyline the sum of angles for all segments, taken modulo 2*PI.

For simplicity, the sheet must be rotated only relatively to the point (0, 0).


The input consists of one or more test cases. Each case starts with a line containing N (1 <= N <= 100). N lines follow, each contains integer coordinates of a point - x and y. They do not exceed 10000 by an absolute value. The polyline may have self-intersections or self-touchings. Polyline contains N - 1 segments, i-th one is directed from point i to point i + 1, no segment has zero length.

The input is terminated by a case with N = 0.


For each case output the minimal possible total angle on the first line. The angle must be in range from 0 to 2*PI. The second line must contain a counter-clockwise rotation angle for the polyline needed to obtain this minimal value. Next N lines must contain coordinates of the points after the rotation. Separate output for subsequent cases with an empty line.

Note that range from 0 to 2*PI for angles means that 0 is included, but 2*PI is not included.

The real numbers in answer must be accurate up to 6 digits after decimal point.

Sample Input

0 0
1 1

Sample Output

0.00000000000000000000 0.00000000000000000000
1.41421356237309505000 -0.00000000000000000000

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6
Submit    Status