ZOJ Problem Set - 2596
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.
2 0 0 1 1 0
0.00000000000000000000 5.49778714378213817000 0.00000000000000000000 0.00000000000000000000 1.41421356237309505000 -0.00000000000000000000
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6