自动搬运

查看原文

来自洛谷，原作者为

	wuzhaoxin FFish

搬运于2025-08-24 21:38:22，当前版本为作者最后更新于2018-12-05 17:23:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

BFS大火题

首先 标签里面写了，那我们就 二分答案

模型转化

把答案视为Boss的攻击半径，题目就变成了给你一个矩形中有一些圆，问能否找到一条从左下角到右上角的路径不经过任何一个圆（此类问题的常规操作）

如果我们把圆看成奶酪上的一些洞，则当左边界或上边界通过这些洞和右边界或下边界联通时问题无解

然后我们看到了[NOIP2017]奶酪

然后就做完了

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
inline int gi() {
    register int x, c, op=1;
    while(c=getchar(),c<'0'||c>'9')if(c=='-')op=-op;
    x=c^48;
    while(c=getchar(),c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48);
    return x*op;
}
int dis[3001][3001];
int x[3001],y[3001];
int getdis(int x1,int y1,int x2,int y2) {
	return pow(x1-x2,2)+pow(y1-y2,2);
}
bool able(int d,double r) {
	return r*r*4>d;
}
int row,line,n;
queue<int>q;
bool vis[3001];
bool bfs(double r) {
	memset(vis,0,sizeof(vis));
	while(!q.empty())q.pop();
	for(int i=1;i<=n;i++)
		if(x[i]<r||row-y[i]<r)q.push(i),vis[i]=1;
	while(!q.empty()) {
		int p=q.front();
		q.pop();
		if(line-x[p]<r||y[p]<r)return 0;
		for(int i=1;i<=n;i++)
			if(!vis[i]&&able(dis[p][i],r))vis[i]=1,q.push(i);
	}
	return 1;
}
int main() {
	n=gi(),line=gi()-1,row=gi()-1;
	for(int i=1;i<=n;i++)
		x[i]=gi()-1,y[i]=gi()-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			dis[i][j]=dis[j][i]=getdis(x[i],y[i],x[j],y[j]);
	double l=0,r=min(row,line),mid;
	for(int i=1;i<=60;i++) {
		mid=(l+r)/2;
		if(bfs(mid))l=mid;
		else r=mid;
	}
	printf("%.2lf\n",l);
	return 0;
}