Given two unordered point sets related by a rotation plus translation, find the smallest counterclockwise rotation angle in [0, 2pi) that maps the first set onto the second.
Hard8GeometrySortingMathImplementationNo attempts yetTime limit8sMemory limit512 MBNod is an astrologist, and he defined a new constellation. To read a friend's fortune he photographed the constellation on two different days. The constellation consists of n stars. The shape in the two photos is the same, but the constellation sits at a different angle in each photo because the photos were taken on different days. Nod reads the fortune from the rotation between the two photos.
Write a program that computes the rotation between the two photos.
Rotating a point (x,y) counterclockwise about the origin by θ moves it to (xcosθ−ysinθ, xsinθ+ycosθ). There is always a θ such that rotating every star of the first photo counterclockwise by θ and then translating all of them lands exactly on the stars of the second photo. If the constellation has rotational symmetry, several such θ exist.
The input is a sequence of datasets. Each dataset is given in the following format:
n
x1,1 y1,1
. . .
x1,n y1,n
x2,1 y2,1
. . .
x2,n y2,n
The first line of each dataset contains a positive integer n (n≤1000). The next n lines contain two real numbers x1,i and y1,i (∣x1,i∣,∣y1,i∣≤100), the coordinates of the i-th star of the constellation in the first photo. The next n lines contain two real numbers x2,i and y2,i (∣x2,i∣,∣y2,i∣≤100), the coordinates of the i-th star of the constellation in the second photo.
The order in which the stars are listed does not matter for deciding that the two shapes are the same. In each photo the distance between every pair of stars is larger than 10−5.
The input ends with a line containing n=0. That line is not part of any dataset, so do not process it.
For each dataset, print the rotation in radians on its own line. Among all θ that map every star of the first photo onto the stars of the second photo by a counterclockwise rotation by θ followed by a translation, print the smallest one that satisfies 0≤θ<2π.
Round the value at the sixth digit after the decimal point and always print six digits after the decimal point, padding with zeros. Print no other character or space.