codeforce514 D. Nature Reserve 凸函数三分

算法 三分法

codeforce514 D. Nature Reserve

给定若干个点，求包含所有点且与x轴相切的圆的最小半径

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;
const double eps=1e-8;
int n;
pair<double,double>a[MAX];
double l,r,midl,midr,lr,rr;
double dis(double x1,double x2,double y2)
{
return (x1-x2)*(x1-x2)+y2*y2;
}
double getr(double x)
{
double R=0.0;
for(int i=0;i<n;++i)
{
double d=dis(x,a[i].first,a[i].second);
R=max(R,fabs(d/a[i].second/2.0));
}
return R;
}
int main()
{
while(~scanf("%d",&n))
{
bool yl=0,yr=0;int yo=0;
l=rr=1e7,r=lr=-1e7;
for(int i=0;i<n;++i)
{
scanf("%lf%lf",&a[i].first,&a[i].second);
l=min(l,a[i].first);
r=max(r,a[i].first);
if(a[i].second>0) yl=1;
else if(a[i].second<0) yr=1;
else ++yo;
}
if((yl&&yr)||yo>1) {printf("-1n");continue;}
if(fabs(l-r)<eps)
{
double R=0.0;
for(int i=0;i<n;++i) R=max(r,fabs(a[i].second));
printf("%.8fn",R/2.0);
continue;
}
for(int i=0;i<100;++i)//100次逼近1e-6
{
midl=l+(r-l)/3.0;midr=r-(r-l)/3.0;//三分
lr=getr(midl),rr=getr(midr);
if(lr-rr>eps) l=midl;
else r=midr;
}
printf("%.8fn",(lr+rr)/2.0);
}
return 0;
}

最后

以上就是机灵星月为你收集整理的codeforce514 D. Nature Reserve 凸函数三分的全部内容，希望文章能够帮你解决codeforce514 D. Nature Reserve 凸函数三分所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。