월드 오브 큐브

시간 제한1초메모리 제한128 MB

요약

상자 안의 N개 초점을 중심으로 하는 같은 크기의 축 정렬 정육면체로 상자 전체를 덮을 때 필요한 최소 모서리 길이를 구한다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 기하, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

직육면체 모양의 3차원 공간이 하나 있고, 이 공간을 ‘홀’이라고 부른다. 홀 안에는 초점(focus) $N$ 개가 주어진다.

각 초점을 중심으로 하고 축에 평행한 정육면체를 하나씩, 모두 $N$ 개 놓는다. 이때 $N$ 개의 정육면체는 변의 길이가 모두 같아야 한다. 정육면체끼리 서로 겹쳐도 되고, 홀의 경계 밖으로 벗어나도 된다.

목표는 이 $N$ 개의 정육면체의 합집합으로 홀 전체를 빈틈없이 덮는 것이다.

초점들이 주어졌을 때, 홀 전체를 덮을 수 있는 정육면체의 변의 길이 중 가장 작은 값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 초점의 개수 $N$ 과 홀의 크기 $X$ , $Y$ , $Z$ 가 공백으로 구분되어 주어진다. ( $1 \le N \le 50$ , $1 \le X, Y, Z \le 10^9$ ) 홀의 한 꼭짓점은 원점 $(0, 0, 0)$ 에 있고, 그 반대편 꼭짓점은 $(X, Y, Z)$ 이다.

이어지는 $N$ 개의 줄에는 각 초점의 좌표 $x$ , $y$ , $z$ 가 주어진다. ( $0 \le x \le X$ , $0 \le y \le Y$ , $0 \le z \le Z$ )

입력의 마지막 줄에는 $0$ 이 네 개 주어지며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

k. D

$k$ 는 테스트 케이스의 번호(1부터 시작)이고, $D$ 는 홀 전체를 덮는 정육면체의 가장 작은 변의 길이이다. $D$ 는 항상 정수이다.

예제3

예제 1

입력

예상 출력

1. 4
2. 6

예제 2
입력
```
1 2 2 2
1 1 1
0 0 0 0
```
예상 출력
```
1. 2
```
예제 3
입력
```
1 2 2 2
0 0 0
0 0 0 0
```
예상 출력
```
1. 4
```