前言
题目传送门 P2218 [HAOI2007] 覆盖问题
题意简述
在一个平面直角坐标系中给定 \(N\) 个点，现在使用三个边长为 \(L\) 正方形将这些点全部覆盖，且正方形的边平行于坐标轴。求 \(L\) 最小值。
思路：二分 + DFS
首先考虑下面的简化问题：使用一个最小矩形覆盖平面直角坐标系内所有点，矩形的边与坐标轴平行，问应该怎么放。这很简单：我们一定能在所有的点中找出最左、最右、最上、最下的四至点，让它们分别位于矩形的四条边上即可。
然后看我们的这个问题。我们需要把刚刚的矩形拆分成三个小正方形，那么显然至少有一个正方形需要覆盖四至点中的两个。并且为了让正方形最小，我们应该用正方形的边去覆盖，并且覆盖一角（如最左和最下）要优于覆盖一条（如最左和最右）。
有了这个思路，我们就可以开始着手写代码了。
先考虑二分部分。答案显然具有单调性：边长越大，能覆盖的点就越多。本题又是经典的最大值最小化模板，就不再赘述。
主要问题是 check() 函数怎么写。按上面的思路，我们按顺序摆放三个正方形：
-
对于第一个，此时所有的点都未覆盖，我们可以把它摆到任意一个角，所以需要枚举四种情况；
-
对于第二个，此时在还未覆盖的点中我们需要摆下两个正方形，那么同样放在一角去覆盖两个四至点是最优的。我们找出新的四至点，同上进行枚举。
-
对于第三个，此时在还未覆盖的点中我们只能放下一个正方形。那么就无所谓优劣了，我们必须保证这最后一个正方形能覆盖所有尚未覆盖的点。那么不用枚举，直接检查边长是否足够即可。
容易看出，上面所说的过程可以用 DFS 实现。于是就可以愉快的打暴搜(bushi DFS 了。
代码
代码如下：
记得开 \(\texttt{long long}\) 哦！
#include<iostream>
#include<cstring>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MIKU 0
using namespace std;const int INF = 1e18;int n, maxx = -INF, minx = INF, maxy = -INF, miny = INF;
struct Point { int x, y; } P[20005];bool cvd[20005]; //标记点是否被覆盖
void addtag(int l, int r, int d, int u, bool tag) { //给点加上已覆盖/未覆盖标记for(int i=1; i<=n; i++) {if(P[i].x >= l && P[i].x <= r && P[i].y >= d && P[i].y <= u) cvd[i] = tag;}
}
bool dfs(int k, int x) {int maxx = -INF, minx = INF, maxy = -INF, miny = INF;for(int i=1; i<=n; i++) if(!cvd[i]) {maxx = max(maxx, P[i].x), minx = min(minx, P[i].x);maxy = max(maxy, P[i].y), miny = min(miny, P[i].y);}if(x >= max(maxx-minx, maxy-miny)) return 1;if(k == 3) return 0; //如果是第三个方形且不满足上面的条件，则边长不足//枚举即可addtag(minx, minx+x, miny, miny+x, 1);if (dfs(k+1, x)) return 1;addtag(minx, minx+x, miny, miny+x, 0);addtag(minx, minx+x, maxy-x, maxy, 1);if (dfs(k+1, x)) return 1;addtag(minx, minx+x, maxy-x, maxy, 0);addtag(maxx-x, maxx, maxy-x, maxy, 1);if (dfs(k+1, x)) return 1;addtag(maxx-x, maxx, maxy-x, maxy, 0);addtag(maxx-x, maxx, miny, miny+x, 1);if (dfs(k+1, x)) return 1;addtag(maxx-x, maxx, miny, miny+x, 0);return 0;
}
bool check(int mid) {memset(cvd, 0, sizeof(cvd));return dfs(1, mid);
} signed main() {fastio;cin>>n;for(int i=1; i<=n; i++) {cin>>P[i].x>>P[i].y;maxx = max(maxx, P[i].x), minx = min(minx, P[i].x);maxy = max(maxy, P[i].y), miny = min(miny, P[i].y);}int l = 0, r = max(maxx-minx, maxy-miny); //注意上界while(l < r) {int mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout<<l;return MIKU;
}