题解 P2498 【[SDOI2012]拯救小云公主】

· · 题解

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;
}