Codeforces Round #514 (Div. 2)(N

链接：https://codeforces.com/contest/1059/problem/D
思路：给n个点，一个半径为r圆包含所有点（包括在圆上）并且与y轴相切，求r的最小值。二分三分都可做，一个一个来。
二分：
枚举半径，然后用射影定理化简得出这个点覆盖的x的坐标，如果所有的x覆盖的区间有交集的话这个圆就存在，并且枚举满足单调性。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+100;

struct point{
    double x,y;
}pp[maxn];
int n;

bool c(double d){
    double maxv = -1e17;
    double minv = 1e17;
    double t;
    for(int i=0;i<n;i++){   
        t = pp[i].y * (2*d - pp[i].y);
        if(t<0)return false; //当比半径2倍还高说明无法走到
        t = sqrt(t);
        maxv = max(maxv,pp[i].x-t);
        minv = min(minv,pp[i].x+t);
    }
    return maxv<=minv;
}

int main(){
    scanf("%d",&n);
    int now = 0;
    int flag = 0;
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&pp[i].x,&pp[i].y);
        if(i==0){
            if(pp[i].y<0)now = -1;
            else now = 1;
        }
        if(i){
            if(now*pp[i].y<0){
                flag = 1;
            }
        }
        pp[i].y = abs(pp[i].y);
    }
    if(flag){
        printf("-1\n");
        return 0;
    }
    double ub = 1e15;
    double lb = 0;
    double ans = 1e15;
    while(fabs(ub-lb)/max(lb,1.0)>1e-7){
         double mid = (ub+lb)/2;
         if(c(mid)){
            ub = mid;
            ans = min(ans,mid);
        }
         else lb = mid;
    }
    printf("%.7f\n",ans);
    return 0;
}

三分：
写出点到圆心的距离，发现是只跟x有关的一个二次函数，满足减增减的性质，考虑枚举x的坐标，然后通过化简可以发现距离跟圆心位置的y坐标无关，然后每次取n个点中距离的最大值返回，三分求一个最小值即可。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+100;
int n;

struct point{
    double x,y;
}pp[maxn];

double c(double d){
    double res = 0;
    for(int i=0;i<n;i++){
        res = max(res,(pp[i].y*pp[i].y+(pp[i].x-d)*(pp[i].x-d))/2.0/pp[i].y);
    }
    return res;
}

int main(){
    scanf("%d",&n);
    int xx = 0,yy = 0;
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&pp[i].x,&pp[i].y);
        if(pp[i].y<0)xx++;
        else yy++;
        pp[i].y = fabs(pp[i].y);
    }
    if(xx&&yy){
        printf("-1\n");
        return 0;
    }
    double ub = 1e7;
    double lb = -1e7;
    while(ub-lb>1e-8){
        double r1 = lb + (ub-lb)/3;
        double r2 = lb + 2*(ub-lb)/3;
        if(c(r1)<c(r2))ub = r2;
        else lb = r1;
    }
    printf("%.7f\n",c(lb));
    return 0;
}