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}$가 순서대로 출력되어야 한다.

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