LuoguP2218 [HAOI2007] 覆盖问题 题解

前言

题目传送门 P2218 [HAOI2007] 覆盖问题
题意简述

在一个平面直角坐标系中给定 \(N\) 个点，现在使用三个边长为 \(L\) 正方形将这些点全部覆盖，且正方形的边平行于坐标轴。求 \(L\) 最小值。
思路：二分 + DFS

首先考虑下面的简化问题：使用一个最小矩形覆盖平面直角坐标系内所有点，矩形的边与坐标轴平行，问应该怎么放。这很简单：我们一定能在所有的点中找出最左、最右、最上、最下的四至点，让它们分别位于矩形的四条边上即可。
然后看我们的这个问题。我们需要把刚刚的矩形拆分成三个小正方形，那么显然至少有一个正方形需要覆盖四至点中的两个。并且为了让正方形最小，我们应该用正方形的边去覆盖，并且覆盖一角（如最左和最下）要优于覆盖一条（如最左和最右）。
有了这个思路，我们就可以开始着手写代码了。
先考虑二分部分。答案显然具有单调性：边长越大，能覆盖的点就越多。本题又是经典的最大值最小化模板，就不再赘述。
主要问题是 check() 函数怎么写。按上面的思路，我们按顺序摆放三个正方形：

• 对于第一个，此时所有的点都未覆盖，我们可以把它摆到任意一个角，所以需要枚举四种情况；
  
• 对于第二个，此时在还未覆盖的点中我们需要摆下两个正方形，那么同样放在一角去覆盖两个四至点是最优的。我们找出新的四至点，同上进行枚举。
  
• 对于第三个，此时在还未覆盖的点中我们只能放下一个正方形。那么就无所谓优劣了，我们必须保证这最后一个正方形能覆盖所有尚未覆盖的点。那么不用枚举，直接检查边长是否足够即可。
  

容易看出，上面所说的过程可以用 DFS 实现。于是就可以愉快的打暴搜(bushi DFS 了。
代码

代码如下：
记得开 \(\texttt{long long}\) 哦！
[code]#include#include#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#define int long long#define MIKU 0using 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= l && P.x = d && P.y >n;        for(int i=1; i>.x>>.y;                maxx = max(maxx, P.x), minx = min(minx, P.x);                maxy = max(maxy, P.y), miny = min(miny, P.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