[CodeForces]1059D Nature Reserve

大意：给你一个平面上N(N<=100000)个点，问相切于x轴的圆，将所有的点都覆盖的最小半径是多少。

计算几何？？？Div2的D题就考计算几何？？？某人昨天上课才和我们说这种计算几何题看见就溜。。。。

打完比赛才发现好像并不用计算几何，实则是一个二分答案的水题。。

发现如果点在x轴两侧就肯定不行，所以我们把所有的点都挪到一侧。

我们二分一个半径，然后发现因为圆相切于x轴，那么这个圆的圆心一定在y=r的直线上移动。

对于所有的点，它可以被如图的线段AC上的点覆盖，点在AC下方也同理。（终于有个图是我自己画的了。。。）

然后发现圆心的取值就在x_i±√(R²-(R-y_i)²)之间。

所以说把每个点的可取圆心的点的集合的交算出来，看看是不是空集，不是空集就可行。

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstdio>

using namespace std;

const double eps=1e-;

int n;

struct Node {int x,y;}node[];

bool flag;

bool ck(double mid) {

    double l=-1e18,r=1e18;

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

        if(node[i].y>mid+mid) return ;

        double range=sqrt(node[i].y*(*mid-node[i].y));

        l=max(l,node[i].x-range);r=min(r,node[i].x+range);

    }

    return (l-r+eps)<=;

}

int main() {

    scanf("%d",&n);

    scanf("%d%d",&node[].x,&node[].y);

    if(node[].y<) flag=;node[].y=abs(node[].y);

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

        scanf("%d%d",&node[i].x,&node[i].y);

        if(flag&&node[i].y>){puts("-1") ;return ;}

        if(flag==false && node[i].y<) {puts("-1");return ;}

        node[i].y=abs(node[i].y);

    }

    double l=,r=1e18;int cnt=;

    while(cnt--) {

        double mid=(l+r)/;

        if(ck(mid)) r=mid;

        else l=mid;

    }

    printf("%lf",l);

}

Nature Reserve

巴特西

[CodeForces]1059D Nature Reserve

最新文章

热门文章