【题目链接】click here~~
【题目大意】求x轴上一点到各点的最大值中的最小值 点到线段距离
【解题思路】三分查找
三分查找初学可以参考这篇博客分析：三分查找，写的很详细了，其实跟类似于二分查找，理解了如何构造，，代码不难实现
方法1：
#include <bits/stdc++.h>using namespace std;const double eps=1e-7;const double inf=0x3f3f3f3f;const int N=55000;int n;struct point{double x,y;}mapp[N];double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double getmax(double x) //最长边，最长时间{double maxx=eps;point q={x,0};for(int i=0;i<n;i++){double p=dis(q,mapp[i]);maxx=max(maxx,p);}return maxx;}int main(){//freopen("1.txt","r",stdin);while(scanf("%d",&n)!=EOF){if(n==0) break;double pleft=N,pright=-N;for(int i=0;i<n;i++){scanf("%lf%lf",&mapp[i].x,&mapp[i].y);pleft=min(pleft,mapp[i].x); //左边界pright=max(pright,mapp[i].x);//右边界}while((pright-pleft)>eps){double mid=(pright-pleft)/3;double l,r;l=pleft+mid,r=pleft+2*mid;if(getmax(l)>=getmax(r)) pleft=l;else pright=r;}printf("%.9f %.9f\n",pleft,getmax(pleft));}return 0;}
方法2：
#include <bits/stdc++.h>using namespace std;const int N=55000;const double eps=1e-7;int n,m;struct point{double x,y;}mapp[N];double disget(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double getmax(double x){//求最大边，最长时间point q={x,0};double maxx=eps;for(int i=0;i<n;i++){double p=disget(q,mapp[i]);maxx=max(maxx,p);}return maxx;}double solve(){//赋初值时，最好直接赋数字！double pleft=-200000,pright=200000;double mid,midd,mid_area,midd_area ;while(pright-pleft>eps){mid=(pleft+pright)/2.0 ;midd=(mid+pright)/2.0 ;mid_area=getmax(mid) ;midd_area=getmax(midd) ;if(mid_area<=midd_area) pright=midd ;else pleft=mid ;}return midd ;}int main(){while(scanf("%d",&n)!=EOF){if(n==0) break;for(int i=0;i<n;i++){scanf("%lf%lf",&mapp[i].x,&mapp[i].y);}double res=solve();printf("%.9f %.9f\n",res,getmax(res));}return 0;}
世上没有绝望的处境，只有对处境绝望的人。
