
D. Nature Reserve
题目链接:https://codeforces.com/contest/1059/problem/D
题意:
在二维坐标平面上给出n个数的点,现在要求一个圆,能够容纳所有的点,并且与x轴相切的最小半径为多少。
题解:
容易知道圆的纵坐标的绝对值等于其半径,并且半径越大,容纳圆的可能性越大,那么就考虑二分其半径,这样y0值也确定了。
但x值不是很好求。这里我们找到y=y0的那一条线,然后根据半径以及y0,yi值,可以求出当x0在哪一段时,能够包含(xi,yi)这个点,这样我们把问题转化一下,就是求区间的交集了。
但是这题卡精度啊。。二分时换种写法,并且记得long double...具体见代码吧:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n,m,x;
struct Point{
ll x,y;
bool operator < (const Point &A)const{
return x<A.x;
}
}p[N];
int check(long double mid){
m=;
long double l=-1e17,r=1e17;
for(int i=;i<=n;i++){
long double ll=fabs(p[i].y-mid);
if(mid*mid<ll*ll) return ;
long double dx = sqrt(mid*mid-ll*ll);
l=max(p[i].x-dx,l);
r=min(p[i].x+dx,r);
}
return l<=r;
}
int main(){
scanf("%d",&n);
int f=;
for(int i=;i<=n;i++){
scanf("%I64d%I64d",&p[i].x,&p[i].y);
if(p[i].y*p[].y<) f=;
}
sort(p+,p+n+);
if(f){
cout<<-;
return ;
}
for(int i=;i<=n;i++) p[i].y=fabs(p[i].y);
long double l=,r=1e16,mid;
for(int i=;i<=;i++){
mid=(l+r)/2.0;
if(check(mid)) r=mid;
else l=mid;
}
if(fabs(l-1e16)<) cout<<-;
else printf("%.15f",(double)l);
return ;
}