codeforces 159 D(几何二分)-蒲公英云

codeforces 159 D(几何二分)

我就是我 2022-05-04 23:58 264阅读 0赞

传送门

题意：给你n个点，问与x轴相切，并且包含这n个点的圆的最小半径是多少。

思路：真是做的的怀疑人生。思路是首先判断点是否在一边。

如果在一边一定有解，二分半径R，这时候圆心在y=R的线上，对于每个点，

我们移动圆就会发现包含这个点吗圆心轨迹是一个线段，我们只需要对每个点的区域

交集，就可以判断存不存在圆心。

但是奇怪的是，本地跟评测机跑的不一样，还有一点不明白的是，

在二分的时候为什么用精度会t，而需要直接设置循环次数。

精度1e-10，这样复杂度是log（1e28）也就100次循环啊，不是很理解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const double eps=1e-10;
const double INF=1e18;
struct Point{
    double x, y;
}p[N];
int n;
bool check(double R){
    double l=-1e9, r=1e9;
    for(int i=1; i<=n; i++){
        if(p[i].y>2.0*R)return false;
        double d=p[i].y-R;
        double dx;
        dx=sqrt(R+d)*sqrt(R-d);
        l=max(l, p[i].x-dx), r=min(r, p[i].x+dx);
        if(l>r) return false;
    }
    return true;
}
int main(){
    scanf("%d", &n);
    bool up=false, down=false;
    for(int i=1; i<=n; i++){
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if(p[i].y>0) up=true;
        else{
            down=true;
            p[i].y=-p[i].y;
        }
    }
    if(up&&down){
        puts("-1");
        return 0;
    }
    double l=0, r=INF, ans=-1;
    for(int i=1; i<=300; i++){
        double mid=(l+r)/2.0;
        if(check(mid)){
            ans=mid;
            r=mid;
        }
        else{
            l=mid;
        }
    }
    printf("%.10lf\n", ans);
    return 0;
}