814 - 3

최근 불어온 TSP(Traveling Salesman Problem)의 열기에 힘입어 다음과 같은 문제를 만들었다:

2차원 평면 위에  $N$개의 도시가 있다. $i$번째 도시의 좌표는 ($x\_i$, $y\_i$)로 나타난다.

회사는 $N$개의 도시를 $K$명의 외판원에게 분배한다. $k$번째 외판원이 받은 도시의 개수를 $c\_k$라고 하자.

각 외판원은 받은 도시를 순회할 순서 $p\_{k,1}$, $p\_{k,2}$, $\cdots$, $p\_{k,c\_k}$를 정하여, $p\_{k,1}$부터 순서대로 모든 도시를 돌고 다시 $p\_{k,1}$로 되돌아온다. 이때, 각 외판원이 이동하는 거리의 최댓값을 최소화하라.

$i$번 도시와 $j$번 도시 사이의 거리 $d(i,j)=\sqrt{(x\_i-x\_j)^2+(y\_i-y\_j)^2}$이며, 문제는 결국 $\max\_{k=1}^{K} {\sum\_{j=1} ^{c\_k} d(p\_{k,j}, p\_{k,j+1})}$를 최소화하는 것이다. 편의상, $p\_{k,c\_k+1}=p\_{k,1}$이다.

첫 번째 줄에 도시의 개수 $N=8 \\; 000$과 외판원의 수 $K=140$가 주어진다.

다음 $N$개의 줄의 $i$번째 줄에는 $i$번 도시의 좌표를 나타내는 두 정수 $x\_i, y\_i$ ($0 \leq x\_i, y\_i \leq 814 \\; 000$)가 주어진다.

주어지는 $x\_i, y\_i$는 주어진 범위 내의 정수 중 하나를 모두 동일한 확률로 선택하여 만들어졌다.

채점에는 총 50개의 입력이 사용되며, 총점은 각 점수의 합이다.

$K$개의 줄에 걸쳐 답을 출력해야 하며, $k$번째 줄에는 $c\_k$, $p\_{k,1}$, $p\_{k,2}$, $\cdots$, $p\_{k,c\_k}$가 순서대로 출력되어야 한다.

출력에서 모든 외판원은 적어도 하나의 도시를 분배받아야 하고, 모든 도시는 정확히 한 번씩 등장해야 한다.