三分

题目

分析

根据题目，在一个二维坐标中，我们要输入N个点坐标，而在x轴（-10000，10000）这个区间存在无数个点，我们假设它为x1,x2,x3…这些点中，每个点到我们输入的N个点的距离存在一个最大值，我们要在这些最大值中找到最小的那一个然后输出。
那么，思路是什么呢？
既然存在这样一个点，那么我们就要找到它所在的那个区间。但是，这里要注意了，是最小值，有最值，而且是最小值，那么就可以用三分法，那为什么不用二分法呢？因为二分法是对与单调区间的，（这在高中大家接触二分法的时候举得例子就是单调函数吧，我记得好像是单调且端点异号。）而三分法是针对有峰值的函数的。显然，在本题中，用三分法是更加方便快捷的。其实，二分法也可以用，就是对分下来的每一个区间进行再次二分。我觉得要用到递归好像。二分法比较复杂一点。后面我掌握后一定会及时向大家分享的。
下面，我们就来介绍一下三分法的解题步骤：
1.首先，我们要将先分为两半，然后在对其中的一变进行再分两半，总体就是2：1：1的形式。这里，我们用mid表示一半，用midmid表示一半的一半。

double check(double x){
    double max=0;
    for(int i=0;i<n;i++){
        double temp=sqrt(a[i].y*a[i].y+(a[i].x-x)*(a[i].x-x));
        if(temp>max)  max=temp;
    }
    return max;
}

我们就是将在x轴坐标的某个点，到所有的N个点的最大值求出并且返回。

double thsearch(double l,double r)
{
    double mid,midmid;
    for(int i=0;i<100;i++){
        mid=l+(r-l)/2;
        midmid=mid+(r-mid)/2;
        if(check(mid)>check(midmid))l=mid;
        else r=midmid;
    }
    return mid;
}

我们先搞清楚这个循环，对于这个循环有人可能会问了？为什么是100，其他可不可以，答案是：可以，我们先讲讲这个原理，每一次循环，都将剩余的区间进行了又一次的三分，这都是2的负次幂级的下降。所以，大家可以想想，2的-100次幂再乘以区间长度的值应该是足够精确的了。其实也可以50，30等。但博主试了一下，好像3也是可以过的，emmm，这就要看测试数据本身了，我们为了保险起见，还是将值设大一点。
然后，对于循环语句块，首先，mid我们代表的是区间中点，而midmid有代表的是区间中点的中点。那这里可能又有人要问了，为什么将midmid放在中点左边呢？其实，你要想，也可以放在中点的右边，只是将代码进行一些细微的修改罢了，更有甚者，还可以两边都来个for循环，emmm，只是，没有必要！

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1),eps=1e-10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n;
struct node{
    int x,y;
}lg[100010];

bool cmp(node a,node b)
{
    return a.x<b.x;
}
double check(double x)
{
    double maxx=0;
    for(int i=0;i<n;i++){
        double tmp=sqrt((lg[i].x-x)*(lg[i].x-x)+lg[i].y*lg[i].y);
        //cout<<tmp<<endl;
        if(tmp>maxx)maxx=tmp;
    }
    return maxx;
}
double thsearch(double l,double r)
{
    double mid,midmid;
    for(int i=0;i<100;i++){
        mid=l+(r-l)/2;
        midmid=mid+(r-mid)/2;
        if(check(mid)>check(midmid))l=mid;
        else r=midmid;
    }
    return mid;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>lg[i].x>>lg[i].y;
    //sort(lg,lg+n,cmp);
    //double l=lg[0].x,r=lg[n-1].x;
    double max=thsearch(-10000,10000);
    printf("%.4f\n",check(max));

    return 0;
}

CSDN博客：https://blog.csdn.net/weixin_43871885/article/details/104344932