대회 풀이

주어진 점의 위치를 (xi,yi) ( i = 1,..,m ) 라 하고 한 군데로 모일 사각형의 위치를 (X,Y) 라 하면 |xi - X| + |yi - Y|의 총합의 최소값을 구하는 문제가 된다.

a ≤ b에 대해 | a - X | + | b - X | 는 a ≤ X ≤ b 일 때 최소임을 쉽게 확인할 수 있다. 이제 양 끝 값씩 짝지어 생각하면 X 는 xi 들의 중간값, Y 는 yi 들의 중간값을 택하면 최소가 됨을 알 수 있다.

1. x 좌표, y좌표를 각각 정렬하여 중간 위치의 값을 택하면 O(M logM)
2. 1~N 의 각 좌표마다 몇 개의 점이 있는지 체크하여 앞에서부터 보면서 절반 이상이 포함되는 위치를 찾으면 O(M+N) 으로 계산이 가능하다.