복잡한 종이접기

G 박사는 종이접기를 연구하고, 도형의 아름다움을 복잡도로 잰다. 도형의 복잡도는 꼭짓점의 개수다. 꼭짓점 개수가 같으면 둘레가 더 긴 쪽이 더 복잡하다.

여기서 다루는 종이는 모두 볼록다각형이고, 정확히 한 번만 접는다. 접을 때는 종이의 한 꼭짓점이 다른 꼭짓점 위에 정확히 놓여야 한다. 서로 다른 두 꼭짓점 $A$와 $B$를 고르면, 접는 선은 선분 $AB$의 수직이등분선이고 이 선이 종이를 두 부분으로 나눈다. $A$가 들어 있는 부분을 접는 선에 대해 대칭이동해 나머지 부분 위에 포갠다. 접은 뒤의 도형은 그대로 남은 부분과 대칭이동한 부분의 합집합이다. 반대로 $B$가 들어 있는 쪽을 접으면 그 도형의 거울상이 나오므로 꼭짓점 개수와 둘레는 같다.

주어진 볼록다각형마다 한 번 접어서 만들 수 있는 가장 복잡한 다각형의 둘레를 출력하는 프로그램을 작성하라.

예제 입력의 첫 번째 데이터는 그림 1의 왼쪽에 있는 직사각형이다. 이 직사각형을 접으면 그림 1-a부터 1-c까지 실선으로 그린 세 가지 다각형이 나온다. 이 데이터의 답은 그림 1-a에 있는 오각형의 둘레다. 그림 1-b의 직사각형이 둘레는 더 길지만 꼭짓점 개수가 먼저다.

주어진 다각형	(a)	(b)	(c)

그림 1: 예제 입력의 첫 번째 데이터

두 번째 데이터는 그림 2의 왼쪽에 있는 삼각형이다. 어느 두 꼭짓점을 고르더라도 그림 2-a부터 2-c까지처럼 사각형이 나온다. 이 중에서 둘레가 가장 긴 것이 답이고, 그림 2-a의 사각형이 여기에 해당한다.

주어진 다각형	(a)	(b)	(c)

그림 2: 예제 입력의 두 번째 데이터

처음에는 볼록다각형이지만 접으면 오목다각형이 나오기도 한다. 그림 3의 왼쪽은 세 번째 데이터의 다각형이다. 이 다각형을 접으면 그림 3의 오른쪽에 있는 오목한 육각형을 얻을 수 있고, 이 도형의 꼭짓점 개수가 가장 많다.

주어진 다각형	접은 도형

그림 3: 예제 입력의 세 번째 데이터

그림 4의 왼쪽은 다섯 번째 데이터의 다각형이다. 그림 4-b의 다각형이 그림 4-a의 다각형보다 둘레가 길지만 사각형이므로, 답은 그림 4-a에 있는 오각형의 둘레다.

주어진 다각형	(a)	(b)

그림 4: 예제 입력의 다섯 번째 데이터

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

n
x1 y1
...
xn yn

$n$은 주어진 다각형의 꼭짓점 개수이며 $3 \le n \le 20$을 만족한다. $(x_i, y_i)$는 $i$번째 꼭짓점의 좌표다. $x_i$와 $y_i$는 $0 \le x_i, y_i < 1000$인 정수다. 꼭짓점 $(x_1, y_1), \dots, (x_n, y_n)$은 $y$축이 위를 향하는 $xy$평면에서 반시계 방향으로 주어진다. 주어지는 다각형은 모두 볼록다각형이다.

주어진 다각형을 접어서 얻을 수 있는 모든 다각형은 다음 두 조건을 만족한다.

• 두 꼭짓점 사이의 거리는 $0.00001$ 이상이다.
• 연속한 세 꼭짓점 $P$, $Q$, $R$에 대해, 점 $Q$와 두 점 $P$, $R$을 지나는 직선 사이의 거리는 $0.00001$ 이상이다.

입력의 끝은 $0$ 하나만 있는 줄로 표시한다.

각 데이터마다 주어진 다각형을 한 번 접어서 얻는 가장 복잡한 다각형의 둘레를 한 줄에 하나씩 출력한다. 소수점 아래 여섯 자리까지 출력하고, 다른 문자는 출력하지 않는다. 테스트 데이터의 모든 답은 반올림 경계에서 충분히 떨어져 있어 여섯째 자리가 하나로 정해진다.