BOJ 13421 국민 랜드

입력으로 4개의 좌표가 주어지면 그 4개의 좌표를 옮겨서
각 변이 x축 또는 y축에 평행하고, 두 대각선의 교점이 (0, 0)이되는 정사각형을 최소비용으로 만들어야 한다. 이 때, 최소비용으로 만들 수 있는 정사각형 중에서 가장 큰 정사각형을 만들어야 하고 그 정사각형의 한 변의 길이를 출력하는 문제이다.

각 좌표를 옮길 때 드는 비용은 |Xold - Xnew| + |Yold - Ynew| 이다.
그리고 입력으로 들어오는 좌표의 범위는 -10억 ~ 10억이다.

이 것을 모든 정사각형에 대해 입력으로 주어진 4개의 좌표와 비교해서 직접 계산해보면서 최소비용으로 만들 수 있는 것 중 가장 큰 것을 찾으면 시간초과가 분명해진다.

그렇다고 이분탐색을 쓰자니...  기준 값도 마땅치 않고... 기준 값에 대해 크냐 작냐에 따라, 차이가 커지는지, 적어지는지에 대한 것이 명확하지 않은 것 같다.
국민대 풀이 슬라이드가 있지만 지금 당장 보기보다는 나중에 다시 생각해보자.