평화의 표지

1960년대 반전 운동을 상징하는 표지 중 하나가 평화의 표지이고, 아래 그림의 왼쪽에 있다. 오른쪽에는 고급 자동차 제조사인 Mercedes Benz의 표지를 회전하고 크기를 바꾼 것이 있다. 두 표지가 닮았다는 점은 자주 지적되어 왔고, 1968년 운동에 참여했던 일부 시위자는 살면서 왼쪽 표지를 오른쪽 표지로 바꾼 것이 아니냐는 비난을 받기도 했다.

옛 시위자들이 동시대 사람들보다 경제적으로 더 성공했는지, 또는 사회적으로 덜 진보적이 되었는지는 따지지 않고, 여기서는 두 선 그림이 얼마나 비슷한지 판정하는 훨씬 중요한 문제를 다룬다. 선분만으로 이루어진 두 그림이 주어진다. 원은 없다. 두 그림의 유사도는 첫 번째 그림에 (1) 위, 아래, 오른쪽, 왼쪽으로 평행 이동하고 (2) 어떤 각도로 회전하고 (3) 어떤 비율로 크기를 바꾸는 조합을 적용했을 때 두 번째 그림에서 정확히 일치시킬 수 있는 선분의 총 개수이다. 예를 들어 주어진 그림에서 원을 빼고 생각하면, 왼쪽 그림을 오른쪽으로 90도 회전하고 오른쪽으로 옮긴 뒤 75%로 크기를 바꾸어 세 개의 선분을 일치시킬 수 있다.

첫 줄에는 입력 데이터 세트의 수 K가 주어지고, 그 뒤에 K개의 데이터 세트가 주어진다. 각 데이터 세트는 다음과 같다.

데이터 세트의 첫 줄에는 첫 번째 그림과 두 번째 그림의 선분 수를 나타내는 두 정수 1 ≤ n, n′ ≤ 50이 주어진다. 다음 줄에는 4n개의 실수 0.0 ≤ xi,1, yi,1, xi,2, yi,2 ≤ 100.0이 주어진다. 첫 번째 그림의 i번째 선분은 (xi,1, yi,1)에서 (xi,2, yi,2)까지이다. 그다음 줄에는 4n′개의 실수 0.0 ≤ x′i,1, y′i,1, x′i,2, y′i,2 ≤ 100.0이 주어지며, 두 번째 그림의 n′개 선분을 같은 방식으로 나타낸다.

각 데이터 세트마다 “Data Set x:”를 한 줄에 출력한다. x는 데이터 세트의 번호이다. 그다음 줄에는 첫 번째 그림을 평행 이동, 회전, 크기 변경하여 두 번째 그림에서 일치시킬 수 있는 선분의 최대 개수를 출력한다. 입력은 0.00001보다 작은 반올림 오차가 결과에 영향을 주지 않도록 주어진다.

각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.