[PS] 2014 Daejeon 6902 Three Squares

본 문제는 여러개의 점들을 정사각형 3개로 모두 감싸는데

가장 작은 정사각형의 변의 길이를 출력하는 문제이다.

3개를 구하는것이라 어려울 수 있는데.

2개라고 생각하면 매우 간단하다.

먼저 위 점들을 모두 포함하는 큰 직사각형을 구한다.

위 와같이 (0,1) (1,0) (2,3) (3,2) (5,2) 의 5개의 점이 있을때

이 점을 모두 포함하는 직사각형을 구한다.

이 직사각형 안에서 2개의 정사각형으로 점들을 모두 감싸려면 정사각형은 반드시 대각선의 꼭지점에 붙어야한다.

그렇다면 다음과 같은 결론이 도출된다.

직사각형안의 점들을 감싸려면 적어도 1개의 정사각형은 꼭지점에 붙어야한다.

위와 같이 사각형의 4 꼭지점중 한곳에 정사각형을 그려 포함되는점을 제거한다.

여기서는 변의 길이를 2로 한 정사각형을 그렸지만,

문제에서는 최소한의 정사각형의 변을 출력해야하므로.

가장작은변은 0 , 가장큰변은 직사각형의 긴변이 되겠다. 이 길이를 M 이라한다면

문제의 답은 0~M 사이가 되겠다. 이 길이들을 이진탐색을 통해 계산하면된다.

남은 점들로 아까와 같은 직사각형을 다시 그린다.

아까도 말했듯이 대각으로 정사각형을 2개그려 점들이 모두 포함되는지를 확인한다.

아까 구한 사각형 1개와 지금 구한 사각형2개로 답을 구할수 있다.