Dadasquare

한 변의 길이 $L$로 점들을 덮을 수 있는지를 먼저 판정하고, $L$을 이분 탐색한다. 점의 좌표가 모두 정수이므로 최적의 $L$도 정수로 선택할 수 있다. 답은 $0$ 이상 $2\cdot 10^9$ 이하이다.

다음에서 점들의 바운딩 박스를 $[x_{\min},x_{\max}]\times[y_{\min},y_{\max}]$라고 하자. 각 정사각형은 이 바운딩 박스 바깥으로 나간 부분을 안쪽으로 밀어서, 해당 변과 맞닿게 놓을 수 있다.

1. 모서리에 정사각형이 있는 경우

점들을 정사각형 두 개로 덮을 수 있다면, 바운딩 박스의 서로 마주 보는 두 모서리에 각각 정사각형을 놓는 해가 존재한다. 두 대각선 방향을 점검하면 되므로 두 개로 덮을 수 있는지는 $O(N)$에 판정한다.

세 개로 덮을 수 있다면, 바운딩 박스의 어떤 모서리에 정사각형 하나를 놓는 해가 존재한다. 모든 점의 상하좌우 극값을 세 개의 정사각형이 덮으므로 어떤 정사각형은 두 방향의 극값을 동시에 덮는다. 두 방향이 인접하면 해당 모서리로 밀 수 있고, 마주 보는 방향이면 바운딩 박스의 그 방향 길이가 $L$ 이하이므로 다시 모서리로 밀 수 있다. 네 모서리 중 하나를 골라 그 정사각형에 덮이지 않은 점들을 위의 두 정사각형 판정으로 확인한다. 이것도 $O(N)$이다.

마찬가지로 네 개 중 어떤 정사각형이 두 방향의 극값을 덮는 경우, 네 모서리에 하나씩 놓아 보고 남은 점을 세 개로 덮을 수 있는지 확인한다. 총 $O(N)$이다.

2. 네 정사각형이 서로 다른 변에 닿는 경우

남은 경우에는 네 정사각형이 각각 왼쪽, 오른쪽, 위쪽, 아래쪽 변에 닿는다. 이들을 $S_L,S_R,S_T,S_B$라고 하자. 의 왼쪽 변은 에, 의 오른쪽 변은 에, 의 위쪽 변은 에, 의 아래쪽 변은 에 맞춘다.

상하를 뒤집는 두 방향을 검사하면, $S_T$가 $S_B$보다 왼쪽에 놓이는 경우만 고려해도 된다.

$S_L$의 윗변의 높이를 $t$라고 두고 고정하자. $S_L$에 덮이지 않은 점들을 $P'$라고 한다. 이때 는 의 가장 왼쪽 점의 좌표를 왼쪽 변으로 하고, 윗변은 에 맞출 수 있다. 그렇지 않으면 다른 정사각형들도 그 가장 왼쪽 점을 덮을 수 없거나, 를 왼쪽으로 밀어도 기존 점들을 잃지 않는다.

이제 $S_T$에도 덮이지 않은 점들의 최소 $x$좌표에 $S_B$의 왼쪽 변을 놓고, 아랫변을 $y_{\min}$에 맞춘다. 나머지 점들의 바운딩 박스의 가로·세로 길이가 모두 이하인지 확인하면 마지막 하나로 덮을 수 있는지 판정된다.

3. 스위핑을 $O(N\log N)$에 구현하기

$S_L$에 포함될 수 있는 점은 $x_i\le x_{\min}+L$인 점뿐이다. 해당 점은 일 때 에 들어간다. 따라서 가 변하면서 점의 포함 여부가 변하는 사건은 점마다 최대 두 개다.

한편 $S_T$와 $S_B$가 덮는 세로 구간은 고정되어 있다. 점들을 다음 네 분류 중 하나에 넣는다.

• 위쪽 구간: $y_i\ge y_{\max}-L$.
• 아래쪽 구간: $y_i\le y_{\min}+L$.

점들을 $x$좌표로 정렬하고 세그먼트 트리를 구성한다. 각 노드는 현재 $S_L$에 덮이지 않은 점들에 대해 네 분류별 바운딩 박스를 유지한다. 점 하나의 포함 상태 변경은 $O(\log N)$에 처리된다. 또한 임의의 $x$ 구간과 분류의 합집합에 대한 바운딩 박스를 에 얻는다.

$S_T$의 왼쪽 변을 $a$라고 하면 $a$는 현재 남은 점들의 최소 $x$좌표이다. $S_T$는 에 있는 위쪽 구간의 점을 덮는다. 이를 제외한 점들의 최소 좌표를 라 하면 의 왼쪽 변이 이다. 는 세그먼트 트리의 전체 또는 구간 질의로 계산한다.

두 정사각형을 더 제거한 뒤의 점들은 $x\ge b$에만 남는다. 남은 점들의 바운딩 박스는 아래 구간들의 합집합으로 구한다.

• $b\le x\le a+L$: 위쪽과 아래쪽 구간 모두에 속하지 않는 점.
• $\max(b,a+L+1)\le x\le b+L$: 아래쪽 구간에 속하지 않는 점.

입력 좌표가 정수이므로 열린 구간의 경계는 위와 같이 정수로 표시할 수 있다. 각 사건 높이에서 새로 들어온 점을 제거한 직후와, 구간에서 빠져나온 점을 되돌린 직후의 상태를 검사한다. 이를 통해 모든 서로 다른 포함 상태를 확인한다.

세그먼트 트리 구성에 $O(N)$, 사건 정렬에 $O(N\log N)$, 최대 $2N$번의 상태 변경과 질의에 $O(N\log N)$이 걸린다. 상하 방향을 뒤집는 경우도 같은 복잡도이다.

따라서 한 번의 판정은 $O(N\log N)$, 이분 탐색까지 포함한 전체 시간복잡도는 $O(N\log N\log 10^9)$이며, 공간복잡도는 $$이다.