다각형 퍼즐

지난해 마라케시에서 열린 ACM ICPC 세계 대회에서 심사위원 한 명이 낙타와 야자수를 그린 나무 퍼즐을 샀다(그림 1). 흔한 직소 퍼즐은 완성된 직사각형 그림을 잘라서 만들지만, 이 퍼즐은 조각마다 따로 자르고 따로 칠했다. 그래서 이웃한 조각끼리 그림이나 색이 이어지지 않는 경우가 많고, 완성한 그림의 바깥 윤곽도 직사각형이 아니다. 이런 퍼즐에서는 조각의 모양이 자리를 알려 주는 유일한 단서일 때가 많다.

심사위원은 그때부터 이 퍼즐을 푸는 프로그램을 짤 수 있을지 궁금해했다. 그런 프로그램에는 두 조각이 얼마나 잘 맞물리는지 재는 방법이 필요하다. 잘 맞물릴수록 실제 퍼즐에서 두 조각이 이웃일 가능성이 크다.

그림 1: 심사위원이 산 나무 퍼즐.

조각은 단순 다각형으로 나타낸다. 주어진 두 다각형을 내부가 겹치지 않고 경계끼리 맞닿도록 놓되, 맞닿은 경계의 길이가 최대가 되게 하여라. 다각형은 평행이동하고 회전할 수 있지만, 뒤집거나 크기를 바꿀 수는 없다.

입력은 다각형 두 개의 정보를 차례로 담는다. 각 다각형의 정보는 꼭짓점 개수 $n$ ($3 \le n \le 50$)이 적힌 줄로 시작한다. 이어지는 $n$개의 줄에는 꼭짓점의 정수 좌표 $x$와 $y$ ($|x|, |y| \le 100$)가 한 줄에 하나씩 주어진다. 각 다각형의 꼭짓점은 시계 방향으로 주어지고, 연속한 세 꼭짓점이 한 직선 위에 놓이는 경우는 없다.

입력 데이터는 꼭짓점을 $10^{-7}$ 이하의 거리만큼 옮기더라도 답이 $10^{-4}$보다 더 커지지 않도록 주어진다.

그림 2: 첫 번째 예제 입력과 그 최적 배치.

두 다각형을 최적으로 놓았을 때 맞닿은 경계의 최대 길이를 소수점 아래 여섯째 자리까지 반올림해 출력한다.