시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4.814 초 814 MB 131 0 0 0.000%

문제

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

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

예제 입력 1

3 2
0 0
3 0
3 1

예제 출력 1

2 3 2
1 1

예제는 $N=3$, $K=2$로 주어졌지만, 채점에서 사용되는 모든 입력은 $N= 8 \; 000$, $K=140$이다.

출처

채점 및 기타 정보

  • 20814000점 이하를 획득해야 를 받는다.
  • 예제는 채점하지 않는다.
  • 맞은 사람의 정렬 기준은 점수의 오름차순이다.