Rotation Estimation

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 MB

Problem

Nod 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 nn 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)(x, y) counterclockwise about the origin by θ\theta moves it to (xcosθysinθ, xsinθ+ycosθ)(x\cos\theta - y\sin\theta,\ x\sin\theta + y\cos\theta). There is always a θ\theta such that rotating every star of the first photo counterclockwise by θ\theta and then translating all of them lands exactly on the stars of the second photo. If the constellation has rotational symmetry, several such θ\theta exist.

Input

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 nn (n1000n \le 1000). The next nn lines contain two real numbers x1,ix_{1,i} and y1,iy_{1,i} (x1,i,y1,i100|x_{1,i}|, |y_{1,i}| \le 100), the coordinates of the ii-th star of the constellation in the first photo. The next nn lines contain two real numbers x2,ix_{2,i} and y2,iy_{2,i} (x2,i,y2,i100|x_{2,i}|, |y_{2,i}| \le 100), the coordinates of the ii-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 10510^{-5}.

The input ends with a line containing n=0n = 0. That line is not part of any dataset, so do not process it.

Output

For each dataset, print the rotation in radians on its own line. Among all θ\theta that map every star of the first photo onto the stars of the second photo by a counterclockwise rotation by θ\theta followed by a translation, print the smallest one that satisfies 0θ<2π0 \le \theta < 2\pi.

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.