Luogu P2218 [HAOI2007] 覆盖问题 题解

前言

题目传送门 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;
}