Gym 2009-2010 ACM ICPC Southwestern European Regional Programming Contest (SWERC 2009) A. Trick or Treat (三分)

题意:在二维坐标轴上给你一堆点,在x轴上找一个点,使得该点到其他点的最大距离最小.
题解:随便找几个点画个图,不难发现,答案具有凹凸性,有极小值,所以我们直接三分来找即可.

代码：

int n;

long double x[N],y[N];

long double check(long double s){

    long double res=0;

    long double tmp;

    for(int i=1;i<=n;++i){

        tmp=sqrt((s-x[i])*(s-x[i])+(y[i]*y[i]));

        if(res<tmp) res=tmp;

    }

    return res;

}

int main() {

    while(scanf("%d",&n)!=EOF){

        if(n==0) break;

        for(int i=1;i<=n;++i){

            scanf("%Lf %Lf",&x[i],&y[i]);

        }

        long double l=-200000,r=200000;

        long double lmid,rmid;

        while(l+eps<r){

            lmid=l+(r-l)/3;

            rmid=r-(r-l)/3;

            if(check(lmid)<check(rmid)) r=rmid;

            else l=lmid;

        }

        printf("%Lf %Lf\n",rmid,check(lmid));

    }

    return 0;

}

巴特西

Gym 2009-2010 ACM ICPC Southwestern European Regional Programming Contest (SWERC 2009) A. Trick or Treat (三分)

最新文章

热门文章