hdu 4766 Network 长春市网络赛 1008 计算几何

可以得出一个结论，得到最优距离的那个点a，要么是目标点，要么就是距离某个点距离为d的点。

第二种情况有两种情形：1：仅仅距离一个点b的距离为d，那么a必定位于目标点到b的连线上。

                                        2：至少距离两个点的距离为d。

那么就可以分别枚举这三种情况了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=1e3+9;
const double inf=1e11,epx=0.00001;
int n;
double rx,ry,d;
double x[maxn],y[maxn];

double cal(double x1,double y1,double x2,double y2)
{
    double a=(x1-x2)*(x1-x2);
    double b=(y1-y2)*(y1-y2);
    return sqrt(a+b);
}

bool chk(double xx,double yy)
{
    for(int i=1;i<=n;i++)
    if(cal(xx,yy,x[i],y[i])>d+epx) return false;
    return true;
}

int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%lf %lf",&rx,&ry)!=EOF)
    {
        scanf("%lf",&d);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        scanf("%lf %lf",&x[i],&y[i]);

        bool flag=false;
        double ans=inf;

        if(chk(rx,ry))
        {
            ans=0;
            flag=true;
        }

        for(int i=1;i<=n;i++)
        {
            double tmp=cal(x[i],y[i],rx,ry);
            double xx=x[i]+(rx-x[i])*(d/tmp);
            double yy=y[i]+(ry-y[i])*(d/tmp);
            if(ans>cal(xx,yy,rx,ry))
            if(chk(xx,yy))
            {
                ans=cal(xx,yy,rx,ry);
                flag=true;
            }
        }



        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(cal(x[i],y[i],x[j],y[j])>2*d+epx) continue;
            if(fabs(x[i]-x[j])<epx&&fabs(y[i]-y[j])<epx) continue;
            double x1=x[j]-x[i];
            double y1=y[j]-y[i];
            double xx=x[i]+x1/2,yy=y[i]+y1/2;
            double tmp=cal(xx,yy,x[i],y[i]);
            double txt=sqrt(d*d-tmp*tmp);
            double ex,ey;
            if(fabs(x1-0)>epx) ey=1,ex=-y1/x1;
            else ex=1,ey=-x1/y1;
            double tt=sqrt(ex*ex+ey*ey);
            xx+=txt*ex/tt;
            yy+=txt*ey/tt;
            if(cal(xx,yy,rx,ry)<ans)
            if(chk(xx,yy))
            {
                ans=cal(xx,yy,rx,ry);
                flag=true;
            }
            xx-=txt*ex*2/tt;
            yy-=txt*ey*2/tt;
            if(cal(xx,yy,rx,ry)<ans)
            if(chk(xx,yy))
            {
                ans=cal(xx,yy,rx,ry);
                flag=true;
            }
        }
        if(!flag) printf("X\n");
        else printf("%.2lf\n",ans);
    }
    return 0;
}

1楼y76182310小时前

这个不是O(n^3)么，弱弱地问句运行时间是多少……

Re: yrleep9小时前

回复y761823n忘了补上运行时间 n1281ms

Re: yrleep9小时前

回复y761823n算上限的话是O(n^3)的。n但是有剪枝，并且判断点符合不符合的时候大多数情况是走不完整个循环的(因为枚举的是边界点)