<JZOJ5904>刺客信条

然鹅考场上打错某变量名导致30都没有

调了很久因为

没转换double

死亡

#include<cstdio>
#include<algorithm>
#include<cmath>
#define rint register int
using std::max;
int x,y,n,fa[2010],s,e;
double ans,l,r,dis[2010][2010],mid;
struct node
{
    int x,y;
} a[2010];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool check(double L)
{
    for(int i=0;i<=n+1;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(dis[i][j]<2*L)
                fa[find(j)]=find(i);
        }
    }
    for(rint i=1;i<=n;++i)
    {
        if(a[i].y-L<0||a[i].x+L>x)     fa[find(s)]=find(i);
        if(a[i].x-L<0||a[i].y+L>y)     fa[find(e)]=find(i);
    }
    return find(s)!=find(e);
}

int main()
{
    freopen("AC.in","r",stdin);
    freopen("AC.out","w",stdout);
    scanf("%d%d%d",&x,&y,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);

    for(rint i=1;i<=n;++i)
        for(rint j=1;j<=n;++j)
            dis[i][j]=dis[j][i]=sqrt((double)(a[i].x-a[j].x)*(double)(a[i].x-a[j].x)+(double)(a[i].y-a[j].y)*(double)(a[i].y-a[j].y));        
            
    s=0;e=n+1;
    l=0,r=sqrt((double)x*x+(double)y*y);
    while(r-l>=0.000001)
    {
        double mid=(l+r)/2;
        if(check(mid))
        {
            ans=mid;
            l=mid;
        }
        else r=mid;
    }
    printf("%.2lf",ans);
    return 0;
}