Tour

모든 점의 볼록 껍질을 구하고, 그 넓이를 $A$라고 하자.

볼록 껍질이 선분이면 점들을 $(X_i,Y_i)$의 사전순으로 정렬하여 출력한다. 이제 볼록 껍질의 넓이가 양수인 경우를 생각하자.

띠의 간격을 $h=\sqrt{\frac{2A}{N}}$으로 정하고, 라고 하자. 다음 두 수평선 격자를 사용한다: 와 . 여기서 는 정수이다.

각 격자에 대해 다음과 같이 후보 순회를 만든다.

1. 각 점을 가장 가까운 격자선에 배정한다.
2. 격자선을 아래에서 위로 보면서, 격자선 번호 $k$가 짝수이면 배정된 점들을 $X$ 오름차순으로, 홀수이면 $X$ 내림차순으로 방문한다.
3. 마지막 점과 첫 점을 연결한다.

두 후보의 순회 길이를 계산하고 더 짧은 후보를 출력한다. 볼록 껍질과 넓이는 $O(N\log N)$에 구할 수 있으므로 전체 시간복잡도는 $O(N\log N)$이다.

Solution written by GPT5.6