题目

传送门

思路

我们发现如果直接算半径不好算

考虑二分半径

因为圆和\(y=0\)相切

所以圆心一定在直线\(y=r\)上面

考虑每个点和圆心的距离一定小于等于\(r\)

所以针对每一个点，我们都可以求出一个区间，使得圆心和点的距离小于等于\(r\)，之后求个交集就行了

这道题精度卡的有点严，所以要将求距离的公式化简一下

代码

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const double eps=1e-9;
struct node
{
    double x;
    double y;
}a[100005];
int n;
int tot;
double l=0,r=1e18,mid;
double f_abs(double x)
{
    return x<0?-x:x;
}
bool check(double cnt)
{
    double lef=-100000000,rig=100000000;
    for(int i=1;i<=n;i++)
    {
        if(f_abs(a[i].y-cnt)>cnt)
            return 0;
        double L=sqrt(a[i].y*(2*cnt-a[i].y)),R;
        R=a[i].x+L;
        L=a[i].x-L;
        if(rig<L||R<lef)
            return 0;
        lef=max(lef,L);
        rig=min(rig,R);
        //printf("%.2lf %.2lf\n",lef,rig);
    }
   // cout<<endl;
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)   
    {
        if(a[i].y>0)
            tot++;
    }
    if(!(tot==n||tot==0))
    {
        cout<<"-1";
        return 0;
    }
    for(int i=1;i<=n;i++)
        a[i].y=f_abs(a[i].y);
    for(int i=1;i<=300;i++)
    {
        mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else
            l=mid;
    }
    printf("%.8lf",mid);
    return 0;
}

习题：Nature Reserve（二分）

原文：https://www.cnblogs.com/loney-s/p/13341260.html