codeforces 159 D(几何二分)

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

[传送门][Link 1]

题意：给你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;
    }

[Link 1]: http://codeforces.com/contest/1059/problem/D