3D 프린팅

시간 제한2초메모리 제한512 MB

요약

겹치지 않는 n개의 정육면체 후보 위치 중 k개를 골라 연결된 다면체를 만들 때, 합집합의 겉넓이가 최소가 되는 값을 구한다.

난이도: 보통10점 중 7점
유형: 그래프, BFS, 조합론
정답자: 아직 제출이 없습니다

문제

3D 프린팅으로 정육면체를 이어 붙인 설치 미술 작품을 만들어 Installation art Contest with Printed Cubes(ICPC)에 출품하려고 한다. 작품은 크기가 같고 방향도 같은 정육면체 정확히 $k$ 개로 이루어진다.

먼저 CAD로 3차원 공간에 정육면체를 놓을 후보 위치 $n$ 개를 잡는다( $n \ge k$ ). 후보 위치 전부에 정육면체를 놓으면 다음 세 조건이 성립한다.

정육면체 하나가 겹치는 다른 정육면체의 개수는 0개, 1개, 2개 중 하나다. 3개 이상과 겹치지는 않는다.
정육면체 하나가 다른 두 정육면체와 겹치면, 그 두 정육면체는 서로 겹치지 않는다.
서로 겹치지 않는 두 정육면체는 면에서도 모서리에서도 꼭짓점에서도 닿지 않는다.

이제 후보 $n$ 개 중 서로 다른 위치 $k$ 개를 골라 정육면체를 놓는다. 이때 정육면체 $k$ 개의 합집합은 연결된 다면체여야 한다. 3D 프린터는 보통 물체의 얇은 겉면만 출력하므로, 필라멘트를 아끼려면 겉넓이가 가장 작은 다면체를 골라야 한다.

후보 $n$ 개 중 $k$ 개를 골라 만들 수 있는 연결된 다면체 가운데 겉넓이가 가장 작은 것의 겉넓이를 구하라.

그림 1. 같은 정육면체를 이어 붙여 만든 다면체.

입력

입력은 여러 개의 데이터 집합으로 이루어진다. 데이터 집합은 최대 100개다. 각 데이터 집합의 형식은 다음과 같다.

n k s
x1 y1 z1
...
xn yn zn

첫 줄의 $n$ 은 후보 위치의 개수, $k$ 는 연결된 다면체를 이룰 정육면체의 개수, $s$ 는 정육면체 한 변의 길이다. $n$ , $k$ , $s$ 는 공백으로 구분한 정수다. 이어지는 $n$ 개의 줄은 후보 위치 $n$ 개를 나타낸다. $i$ 번째 줄의 정수 $x_i$ , $y_i$ , $z_i$ 는 그 위치에 정육면체를 놓았을 때 좌표가 가장 작은 꼭짓점의 좌표이며, 공백으로 구분한다. 정육면체의 모서리는 세 좌표축 가운데 하나와 나란하다.

$1 \le k \le n \le 2000$ , $3 \le s \le 100$ , $-4 \times 10^7 \le x_i, y_i, z_i \le 4 \times 10^7$ 이다. 후보 위치는 위에 적은 세 조건을 항상 만족한다.

입력의 끝은 공백으로 구분한 0 세 개가 있는 줄이다.

출력

각 데이터 집합마다 겉넓이가 가장 작은 연결된 다면체의 겉넓이를 정수 하나로 한 줄에 출력한다. 정육면체 $k$ 개로 연결된 다면체를 만들 수 없으면 -1을 출력한다.

예제4

예제 1

입력

1 1 100
100 100 100
6 4 10
100 100 100
106 102 102
112 110 104
104 116 102
100 114 104
92 107 100
10 4 10
-100 101 100
-108 102 120
-116 103 100
-124 100 100
-132 99 100
-92 98 100
-84 100 140
-76 103 100
-68 102 100
-60 101 100
10 4 10
100 100 100
108 101 100
116 102 100
124 100 100
132 102 100
200 100 103
192 100 102
184 100 101
176 100 100
168 100 103
4 4 10
100 100 100
108 94 100
116 100 100
108 106 100
23 6 10
100 100 100
96 109 100
100 118 100
109 126 100
118 126 100
127 118 98
127 109 104
127 100 97
118 91 102
109 91 100
111 102 100
111 102 109
111 102 118
111 102 91
111 102 82
111 114 96
111 114 105
102 114 114
93 114 114
84 114 105
84 114 96
93 114 87
102 114 87
10 3 10
100 100 100
116 116 102
132 132 104
148 148 106
164 164 108
108 108 108
124 124 106
140 140 104
156 156 102
172 172 100
0 0 0

예상 출력

예제 2

입력

1 1 3
0 0 0
2 2 3
0 0 0
2 0 0
2 1 3
0 0 0
2 0 0
2 2 3
-40000000 -40000000 -40000000
-39999998 -40000000 -40000000
2 2 100
40000000 40000000 40000000
39999901 39999999 39999999
0 0 0

예상 출력

예제 3

입력

예상 출력

-1
-1
-1

예제 4

입력

예상 출력