B.牛牛战队的比赛地

题意：给定n个坐标，求x轴上任意一点到各个点距离最大值的最小值。

题解：分析可以发现x轴一点到各个点距离最大值由大变小再变大，所以我们要求的是一个极小值点。极小值点我们可以用三分来求。每次比较check(midl)和check(midr)的大小。

三分算法：先以left和right为端点计算出它们的中点midl，然后再以midl和right为端点计算出它们的中点midr，接下来就需要判断f(midl)和f(midr)值的大小了，如果f(midl)大于f(midr)，那么说明midl靠近极值，此时令right=midr，否则说明midr靠近极值，此时则令left=midl，总之就是要保留离极值最近的那一个mid，然后重复前面的过程，直到left和right十分接近，最终f(left)就等于了极值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n;
pair<double, double> p[maxn];
double check(double x)
{
    double mx = 0;
    for (int i = 0; i < n; i++)
    {
        double tmp = sqrt((p[i].first - x) * (p[i].first - x) + p[i].second * p[i].second);
        mx = max(mx, tmp);
    }
    return mx;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].first, &p[i].second);
    double l = -10000.0, r = 10000.0;
    double midl, midr;
    for (int i = 0; i < 100; i++)
    {
        midl = l + (r - l) / 2.0;
        midr = midl + (r - midl) / 2.0;
        if (check(midl) > check(midr))
            l = midl;
        else
            r = midr;
    }
    printf("%.6lf\n", check(midl));
    return 0;
}

这题同样可以用二分来写，二分x轴上任意一点到各个点的距离最大值。check(x)：其中x表示各个点到x轴距离，我们可以发现已知点的坐标和到x轴的距离，可以算出x轴上点的区间，如果各个点形成的区间有交集那么check(x)返回true，可以参考我这篇文章的A题。https://blog.nowcoder.net/n/1192b160dc2248889b4057cddfc9fc8b

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
#define eps 1e-6
int n;
pair<double,double> p[maxn];
bool check(double x)
{
    double l = -1.0*INF,r = 1.0*INF;
    for(int i=0;i<n;i++)
    {
        if(fabs(p[i].second)>x)
            return false;
        double x1 = p[i].first-(double)sqrt(x*x-p[i].second*p[i].second);  
        double x2 = p[i].first+(double)sqrt(x*x-p[i].second*p[i].second);
        l = max(l,x1);
        r = min(r,x2);
    }
    return l<=r;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lf%lf",&p[i].first,&p[i].second);
    double l = 0.0, r = 1.0 * INF ;
    for(int i=0;i<100;i++)
    {  
        double mid=(l+r)/2.0;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.6lf\n",l);
    return 0;
}