bzoj1052: [HAOI2007]覆盖问题
先二分边长，然后按这样的策略判断：正方形肯定是选边上的四个角，枚举第一块在哪个角，再算一边四个角，再枚举第二块，判断剩下的能不能被第三块覆盖
const int N = 20010;pair<int, int> Data[N];int n;inline void Input() {scanf("%d", &n);For(i, 1, n) scanf("%d%d", &Data[i].ft, &Data[i].sd);}int Mark[N];inline bool Solve(int R, int Dep) {int Up = -MIT, Down = MIT, Left = MIT, Right = -MIT, flag = 0;For(i, 1, n)if(!Mark[i]) {flag = 1;int X = Data[i].ft, Y = Data[i].sd;Up = max(Up, Y), Down = min(Down, Y),Left = min(Left, X), Right = max(Right, X);}if(!flag) return 1;if(Dep > 2) return R >= max(Up - Down, Right - Left);else {int Ox1, Ox2, Oy1, Oy2;For(type, 1, 4) {if(type == 1) Ox1 = Left, Ox2 = Left + R, Oy1 = Down, Oy2 = Down + R;else if(type == 2) Ox1 = Left, Ox2 = Left + R, Oy1 = Up - R, Oy2 = Up;else if(type == 3) Ox1 = Right - R, Ox2 = Right, Oy1 = Down, Oy2 = Down + R;else Ox1 = Right - R, Ox2 = Right, Oy1 = Up - R, Oy2= Up;// markFor(i, 1, n)if(!Mark[i]) {pair<int, int> *Dat = &Data[i];if(Dat->ft >= Ox1 && Dat->ft <= Ox2 &&Dat->sd >= Oy1 && Dat->sd <= Oy2) Mark[i] = Dep;}if(Solve(R, Dep + 1)) return 1;For(i, 1, n)if(Mark[i] == Dep) Mark[i] = 0;}}return 0;}inline void Solve() {// get MaxDisint Up = -MIT, Down = MIT, Left = MIT, Right = -MIT;For(i, 1, n) {int X = Data[i].ft, Y = Data[i].sd;Up = max(Up, Y), Down = min(Down, Y),Left = min(Left, X), Right = max(Right, X);}int mid, ans = INF, lef = 0, rig = max(Up - Down, Left - Right);while(lef <= rig) {mid = (lef + rig) >> 1;clr(Mark, 0);if(Solve(mid, 1)) rig = (ans = mid) - 1;else lef = mid + 1;}printf("%d\n", ans);}int main() { #ifndef ONLINE_JUDGE SETIO("1052"); #endif Input(); Solve(); return 0;}?