L. Square Annulus

L.pdf

문제에 중요한 명제가 있다.

주어진 $N$개의 점들을 모두 덮는 최소 크기의 정사각형으로, $N$개의 점을 모두 덮을 수 있는 최소 두께의 정사각형 액자를 만들 수 있다.

문제 설명에 따르면 위 명제는 이미 증명된 사실이며, 이 조건 없이 문제를 해결하기는 매우 힘들다.

$w \leq w'$ 일 때, 두께 $w$가 모든 점을 덮으면 두께 $w'$도 모든 점을 덮을 수 있다. 따라서 답을 binary search로 구할 수 있다.

우선, 편의상 $max_x-min_x \leq max_y-min_y$ 라 하자.

그러면 액자의 바깥 정사각형의 한 변 길이 $S = max_y-min_y$ 임과 동시에 액자 위의 y좌표와 아래의 y좌표가 결정된다.

이제 두께 $w$가 답이 될 수 있는지 확인해야한다.

이 때, 여러가지 관점으로 접근할 수 있는데 문제를 풀며 가장 편하다고 느낀 것은 중심의 x좌표를 결정하는 방식이다.

우선 중심의 x좌표를 $X$라 하며 $X$가 될 수 있는 범위는 $[max_x-S/2,min_x+S/2]$이다.

$min_y+w < y_i < max_y-w$ 인 $i$에 대하여, $x_i$들을 정렬한 배열 $A$를 만든다.

액자의 작은 정사각형 한 변 길이는 $S-2w$이다.

두께가 $w$인 액자가 존재하기 위해서 $A_{i+1}-A_i \geq S-2w$ 인 $i$를 찾아야한다.

이 때, 가능한 $X$의 범위를 구해보면, $[A_i+\frac{S-2w}{2},A_{i+1}-\frac{S-2w}{2}]$ 이다.

처음에 구한 $X$의 범위와 $i$에 대한 $X$의 범위 중 공통 범위가 있으면, 두께 $w$는 답이 된다.

처음에 입력받은 좌표에 2를 곱해서 처리하면 double 연산을 할 필요가 없다.

만약 $max_x-min_x > max_y-min_y$ 인 경우 x좌표와 y좌표를 swap 해주면된다.

L.cpp

작은 데이터를 통해 답이 나오는지 확인해볼 수 있다.

input1.txt

output1.txt