회전과 평행이동으로 관계된 두 점 집합이 주어질 때, 첫 집합을 둘째 집합으로 보내는 [0, 2pi) 범위의 가장 작은 반시계 회전각을 구한다.
어려움8기하정렬수학구현아직 제출이 없습니다시간 제한8초메모리 제한512 MBNod는 점성술사이고, 새로운 별자리를 하나 정의했다. 친구의 운세를 보려고 이 별자리를 서로 다른 두 날에 촬영했다. 별자리는 별 n개로 이루어진다. 두 사진에 담긴 별자리의 모양은 같지만, 촬영한 날이 달라서 별자리가 놓인 각도가 다르다. Nod는 두 사진 사이의 회전각으로 운세를 읽는다.
두 사진 사이의 회전각을 구하는 프로그램을 작성하라.
평면의 점 (x,y)를 원점 중심으로 반시계 방향으로 θ만큼 회전하면 (xcosθ−ysinθ, xsinθ+ycosθ)로 옮겨진다. 첫 번째 사진의 별 전체를 반시계 방향으로 θ만큼 회전한 다음 평행이동하면 두 번째 사진의 별 전체와 정확히 겹치는 θ가 항상 존재한다. 별자리가 회전 대칭이면 이런 θ가 여러 개 있다.
입력은 데이터셋 여러 개로 이루어진다. 각 데이터셋의 형식은 다음과 같다.
n
x1,1 y1,1
. . .
x1,n y1,n
x2,1 y2,1
. . .
x2,n y2,n
첫 줄에 양의 정수 n (n≤1000)이 주어진다. 이어지는 n개 줄에는 실수 x1,i와 y1,i (∣x1,i∣,∣y1,i∣≤100)가 주어지고, 이는 첫 번째 사진에서 i번째 별의 좌표다. 그다음 n개 줄에는 실수 x2,i와 y2,i (∣x2,i∣,∣y2,i∣≤100)가 주어지고, 이는 두 번째 사진에서 i번째 별의 좌표다.
두 별자리가 같은 모양인지 볼 때 별이 주어지는 순서는 상관없다. 각 사진에서 서로 다른 두 별 사이의 거리는 모두 10−5보다 크다.
n=0인 줄이 나오면 입력이 끝난다. 이 줄은 데이터셋이 아니므로 처리하지 않는다.
각 데이터셋마다 회전각을 라디안으로 한 줄에 출력한다. 첫 번째 사진의 별 전체를 반시계 방향으로 θ만큼 회전한 뒤 평행이동해서 두 번째 사진의 별 전체와 겹치게 만드는 θ 중, 0≤θ<2π인 값 가운데 가장 작은 것을 출력한다.
값은 소수점 아래 여섯째 자리에서 반올림하고, 자리가 비면 0을 채워 소수점 아래를 항상 여섯 자리로 출력한다. 그 밖의 문자나 공백은 출력하지 않는다.