회전각 추정

회전과 평행이동으로 관계된 두 점 집합이 주어질 때, 첫 집합을 둘째 집합으로 보내는 [0, 2pi) 범위의 가장 작은 반시계 회전각을 구한다.

어려움8기하정렬수학구현아직 제출이 없습니다시간 제한8초메모리 제한512 MB

문제

Nod는 점성술사이고, 새로운 별자리를 하나 정의했다. 친구의 운세를 보려고 이 별자리를 서로 다른 두 날에 촬영했다. 별자리는 별 nn개로 이루어진다. 두 사진에 담긴 별자리의 모양은 같지만, 촬영한 날이 달라서 별자리가 놓인 각도가 다르다. Nod는 두 사진 사이의 회전각으로 운세를 읽는다.

두 사진 사이의 회전각을 구하는 프로그램을 작성하라.

평면의 점 (x,y)(x, y)를 원점 중심으로 반시계 방향으로 θ\theta만큼 회전하면 (xcosθysinθ, xsinθ+ycosθ)(x\cos\theta - y\sin\theta,\ x\sin\theta + y\cos\theta)로 옮겨진다. 첫 번째 사진의 별 전체를 반시계 방향으로 θ\theta만큼 회전한 다음 평행이동하면 두 번째 사진의 별 전체와 정확히 겹치는 θ\theta가 항상 존재한다. 별자리가 회전 대칭이면 이런 θ\theta가 여러 개 있다.

입력

입력은 데이터셋 여러 개로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n
x1,1 y1,1
. . .
x1,n y1,n
x2,1 y2,1
. . .
x2,n y2,n

첫 줄에 양의 정수 nn (n1000n \le 1000)이 주어진다. 이어지는 nn개 줄에는 실수 x1,ix_{1,i}y1,iy_{1,i} (x1,i,y1,i100|x_{1,i}|, |y_{1,i}| \le 100)가 주어지고, 이는 첫 번째 사진에서 ii번째 별의 좌표다. 그다음 nn개 줄에는 실수 x2,ix_{2,i}y2,iy_{2,i} (x2,i,y2,i100|x_{2,i}|, |y_{2,i}| \le 100)가 주어지고, 이는 두 번째 사진에서 ii번째 별의 좌표다.

두 별자리가 같은 모양인지 볼 때 별이 주어지는 순서는 상관없다. 각 사진에서 서로 다른 두 별 사이의 거리는 모두 10510^{-5}보다 크다.

n=0n = 0인 줄이 나오면 입력이 끝난다. 이 줄은 데이터셋이 아니므로 처리하지 않는다.

출력

각 데이터셋마다 회전각을 라디안으로 한 줄에 출력한다. 첫 번째 사진의 별 전체를 반시계 방향으로 θ\theta만큼 회전한 뒤 평행이동해서 두 번째 사진의 별 전체와 겹치게 만드는 θ\theta 중, 0θ<2π0 \le \theta < 2\pi인 값 가운데 가장 작은 것을 출력한다.

값은 소수점 아래 여섯째 자리에서 반올림하고, 자리가 비면 0을 채워 소수점 아래를 항상 여섯 자리로 출력한다. 그 밖의 문자나 공백은 출력하지 않는다.