[PS] 2012 Daejeon 6121 Square Annulus

TL이 10초짜리라 그런지, 설명이 좀 길다. 잘 보면된다.

문제를 간단히 요약하면, 모든점을 포함하는 정사각형을 그린후

내부점을 외곽으로 삼는 작은 정사각형을 그린다.

그런데 작은 정사각형은 큰 정사각형 중심에 위치하여야 한다.

이떄 가장작은 정사각형을 구하고, 문제에서 보듯이 width를 출력하면 된다.

먼저 큰 정사각형의 변의 길이를 구한다.

가장작은 X와 가장큰 X를 구하고 , 가장큰 Y와 가장작은 Y를 구한후

두 거리중에 큰 값을 큰 정사각형의 빗변으로 삼으면 된다.

그림에서 보듯이 Y축의 점들이 더 많이 퍼져있어 큰정사각형의 위아래변이 점을 지난다고

가정하자.

!!문제에서 작은 정사각형 크기에 제한을 두었다. 작은 정사각형의 변의 길이는,

큰 정사각형의 변의길이의 반을 넘지 않는다.

여기서 큰 정사각형의 변의 길이를 D라 하고, width 를 W라 하자.

그럼 작은 정사각형의 변의 길이는 0이상 D/2 이하이다.

이 범위에서 위의 조건이 맞는지 검사하면된다. 당연히 이분검사 를 통해 검사한다.

우선 작은정사각형안에 들어갈수 있는 점들을 선택한다.

minY(가장작은 Y값) , maxY(가장큰 Y값)

minY + W < point.y < maxY - W

위의 그림에서 보듯이 분홍색사각형안에있는 점들을 뽑아낸다.

그후 X값을 기준으로 오름차순 정렬을 한다.

우리는 중점을 찾지 않는다.

변의 길이가 W인 정사각형은 위의 핑크색 사각형안에 존재할수 있다
(전부 다는 아님 밑에서 설명함)

근데, 작은 정사각형안에 다른 점이 들어가면 안되므로...

1. X[i] - X[i-1] > D-2W

조건1을 반드시 만족 하여야한다.

두번째로 핑크색 사각형안에 모든 구간에 존재할 수 없다.

그 이유는 밑의 그림을 보면 안다.

파란색 사각형은 왼쪽으로 최대한 밀었을때 모습이고,

빨간색 사각형은 오른쪽으로 최대한 밀었을떄 모습이다.

그럼 작은 정사각형이 존재할수 있는 범위를 알수있다.

바로 그림에서 핑크색 사각형들이다. ( 당연 그 사이도 된다)

그럼 중점의 범위는 그림에서 보라색 구간이다.

중점의 범위를 수식으로 적으면

max-D/2 부터 minX + D/2 이다. 각각 L과 R이라 하겠다.

그럼 조건 1을 통과한 X[i-1] 에서 핑크색 사각형변의 길이의 절반을 더한값이

중점의 범위에 속하여야 한다.

즉 X[i-1] + (D-2W)/2 <= R

X[i] - (D-2W)/2 >= L

이면 변의 길이가 W인 작은 정사각형이 가능하다는것을 증명한다.

이 증명을 이용해

가능한 W에 대해 이분검색으로 검사하면 답이 나온다.

tip1 : 입력받을때 모든 좌표에 대해 2를 곱하면 double 처리를 없앨 수 있다.

tip2 : 만일 maxY - minY 의 값보다 maxX - minX 가 크다면

좌표평면을 회전시키면된다. 위아래가 더 길도록

즉 모든 좌표를 x,y를 서로 바꾸면된다.