首页 > 代码库 > UVALive 6168 Fat Ninjas --二分小数+搜索

UVALive 6168 Fat Ninjas --二分小数+搜索

2024-07-16 14:13:04   220人阅读

题意：一个NxN的网格地板，有一些激光束从天花板垂直射向地面的某个网格，一个圆要安全地从左走到右，不碰到上边界，下边界以及激光束，问这个圆的直径最大能达到多大。

分析：可以二分直径，关键在check函数的写法。可以讲这个圆缩成一个点，把圆的直径转化为激光的扫描范围，当激光范围完全堵死一条通道的时候，这个直径则是不可行的。怎样判断是否堵死一条通道了呢。每次check(dis)的时候，枚举激光束对，如果激光束之间距离小于dis，那么它们两个之间建一条边。还要注意处理边界，如果激光束范围与上边界或下边界相交，那么边界与这个激光束也建一条边。最后从一个边界dfs到另一个边界，如果能够dfs到，那么说明此时通道被堵死，此dis是不行的。继续二分就能得到答案。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>using namespace std;#define N 5007struct node{    int x,y;}p[N];double d[N][N];vector<int> G[N];int n,L;int vis[N],S,E;double dis(node ka,node kb){    return (double)sqrt((ka.x-kb.x)*(ka.x-kb.x)+(ka.y-kb.y)*(ka.y-kb.y));}int dfs(int u,int fa){    if(u == E)        return 1;    vis[u] = 1;    for(int i=0;i<G[u].size();i++)    {        int v = G[u][i];        if(v == fa)            continue;        if(vis[v])            continue;        if(dfs(v,u))            return 1;    }    return 0;}bool check(double D){    S = 0;    E = L+1;    for(int i=0;i<=L+1;i++)        G[i].clear();    for(int i=1;i<=L;i++)    {        if(p[i].y < D)            G[S].push_back(i);        if(p[i].y + D > n)            G[i].push_back(E);        for(int j=i+1;j<=L;j++)        {            if(d[i][j] < D)            {                G[i].push_back(j);                G[j].push_back(i);            }        }    }    memset(vis,0,sizeof(vis));    if(dfs(S,-1))        return 0;    return 1;}int main(){    int i,j;    while(scanf("%d%d",&n,&L)!=EOF && n)    {        for(i=1;i<=L;i++)            scanf("%d%d",&p[i].x,&p[i].y);        for(i=1;i<=L;i++)            for(j=i+1;j<=L;j++)                d[i][j] = dis(p[i],p[j]);        double low = eps;        double high = n;        while(low+eps < high)        {            double mid = (low+high)/2.0;            if(check(mid))                low = mid;            else                high = mid;        }        printf("%.3lf\n",low);    }    return 0;}
View Code

 


联系
我们