I. Three Squares

2차원 평면에 점들이 $N$개 주어졌을 때, 동일한 크기인 정사각형 세 개로 모든 점들을 덮을 때 가능한 정사각형의 최소 크기를 구하는 문제다.

주어진 $N$개의 점을 포함하는 최소 직사각형을 생각하자. 서로 다른 점이 4개 이상일 때 아래와 같은 명제가 성립한다.

최소 크기의 정사각형 세 개로 모든 점을 덮을 때, 그 정사각형 중 하나는 직사각형의 네 꼭지점 중 하나의 점을 꼭지점으로 한다.

비슷한 상황으로 최소 크기의 정사각형 두 개로, 서로 다른 점 3개 이상을 모두 덮는다고 할 때, 아래와 같은 명제가 성립한다.

최소 크기의 정사각형 두 개로 모든 점을 덮을 때, 두 정사각형은 서로 대각으로 마주보는 두 꼭지점을 꼭지점으로 한다.

이분 검색으로 정사각형의 크기 $s$를 정하고 모든 점을 덮을 수 있는지 $O(N)$ 만에 확인할 수 있다. 따라서, 총 시간복잡도는 $O(N \lg X)$가 된다. 여기서 $X$는 좌표계의 크기다.

#include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define MAXN 100005 #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef long long lld; int T, N, W, H; struct Z{ Z(int x=0, int y=0): x(x), y(y) {} int x, y; bool operator < (const Z &ot)const{ return x != ot.x ? x < ot.x : y < ot.y; } bool operator == (const Z &ot)const{ return x == ot.x && y == ot.y; } }; vector <Z> A; bool proc2(int m, vector<Z> &arr) { if (sz(arr) < 3) return 1; bool sw = 0; int mnx = 2e9, mny = 2e9, h = 0, w = 0; for (Z &p: arr){ if (mnx > p.x) mnx = p.x; if (mny > p.y) mny = p.y; } for (Z &p: arr){ p.x -= mnx; p.y -= mny; if (w < p.x) w = p.x; if (h < p.y) h = p.y; } for (Z &p: arr){ if (!(p.x <= m && p.y <= m) && !(p.x >= w-m && p.y >= h-m)){ sw = 1; break; } } if (!sw) return 1; sw = 0; for (Z &p: arr){ if (!(p.x >= w-m && p.y <= m) && !(p.x <= m && p.y >= h-m)){ sw = 1; break; } } return !sw; } bool proc(int m) { vector <Z> tmp; for (Z &p: A){ if (!(p.x <= m && p.y <= m)) tmp.push_back(p); } if (proc2(m, tmp)) return 1; tmp.clear(); for (Z &p: A){ if (!(p.x <= m && p.y >= H-m)) tmp.push_back(p); } if (proc2(m, tmp)) return 1; tmp.clear(); for (Z &p: A){ if (!(p.x >= W-m && p.y <= m)) tmp.push_back(p); } if (proc2(m, tmp)) return 1; tmp.clear(); for (Z &p: A){ if (!(p.x >= W-m && p.y >= H-m)) tmp.push_back(p); } if (proc2(m, tmp)) return 1; return 0; } int main() { int i; for (scanf("%d", &T);T--;){ scanf("%d", &N); A.clear(); int mnx = 2e9, mny = 2e9; for (i=1;i<=N;i++){ int x, y; scanf("%d%d", &x, &y); A.emplace_back(x, y); if (mnx > x) mnx = x; if (mny > y) mny = y; } sort(all(A)); A.erase(unique(all(A)), A.end()); if (sz(A) < 4){ puts("0"); continue; } W = H = 0; for (Z &p: A){ p.x -= mnx; p.y -= mny; if (W < p.x) W = p.x; if (H < p.y) H = p.y; } lld s = 0, e = max(H, W); int ans = 0; while (s <= e){ lld m = (s+e)>>1; if (proc(m)) e = m-1, ans = m; else s = m+1; } printf("%d\n", ans); } }