외교 특권

외교 비용을 최소화하기 위해 세계 각국은 다음과 같이 논의하였다. 각 나라가 최대 한 나라와만 외교 관계를 맺는 것으로는 충분하지 않다. 세계에는 나라가 둘보다 많으므로, 그럴 경우 어떤 두 나라는 외교관들의 연쇄를 통해서도 서로 연락할 수 없기 때문이다.

그래서 각 나라가 최대 두 나라와 외교 관계를 맺는다고 하자. 모든 나라를 동등하게 대우해야 한다는 것이 외교상 불문율이므로, 결국 각 나라는 정확히 두 나라와 외교 관계를 맺는다.

이 조건을 만족하는 구조로 다음이 제안되었다. 모든 나라를 원형으로 배치하고, 각 나라가 자신의 왼쪽 이웃 및 오른쪽 이웃과 외교 관계를 맺도록 한다. 각 나라의 외교부는 그 나라의 수도에 있으며, 편의상 2차원 평면 위의 한 점으로 주어진다고 하자. 외교 관계를 맺은 두 나라의 외교부를 선분으로 이으면 하나의 다각형이 만들어진다.

이제 양자 외교 회담을 열 장소를 정해야 한다. 외교상의 이유로 두 나라의 외교관이 회담 장소까지 이동하는 거리는 서로 같아야 하며, 효율을 위해 그 거리는 가능한 한 작아야 한다. 모든 회담 장소를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 관련된 나라의 수 $n$으로 시작한다. $n \ge 3$이며 홀수임이 보장된다. 이어서 각 나라 외교부의 위치를 나타내는 $x$좌표와 $y$좌표의 쌍이 $n$개 주어진다. 모든 좌표는 절댓값이 $10^{12}$보다 작은 정수이다. 나라들은 원을 따라 놓인 순서대로 주어지며, 추가로 첫 번째 나라는 목록의 마지막 나라와 이웃이다. 입력은 파일의 끝(EOF)에서 종료된다.

각 테스트 케이스에 대해, 회담 장소의 개수(이는 $n$과 같다)를 출력한 뒤 각 장소의 $x$좌표와 $y$좌표를 출력한다. 회담 장소는 입력과 같은 순서로, 즉 첫 번째와 두 번째 나라의 회담 장소부터 시작하여 연속된 나라 쌍의 순서대로 출력하고, 마지막으로 $n$번째 나라와 첫 번째 나라의 회담 장소를 출력한다. 모든 좌표는 소수점 아래 여섯 자리까지 출력한다.

회담 장소들을 입력 순서대로 나열하면 그 자체로 하나의 다각형으로 볼 수 있다. 나라들로부터 회담 장소를 구하는 것과, 회담 장소들로부터 원래의 나라들을 복원하는 것은 서로 역의 문제이다.