(\)
(Description)
你现在有(N)个分布在二维平面上的整点((x_i,y_i))，现在需要你找到一个圆，满足：
- 能够覆盖所有的给出点
- 与(x)轴相切
现在需要你确定合法的圆的最小半径是多少，精度误差允许在(10^{-6})范围内。
如果不存在一个合法的圆，输出(-1)。
- (Nin [1,10^5]，x_i,y_iin [10^{-7},10^7])
(\)
(Solution)
垃圾 (Double) 毁我青春
首先考虑哪些情况不合法。显然如果点全部在(x)轴同一侧显然有解，所以只需要判断所有(y_i)是否同号即可。
便于处理，我们将所有点都放到(x)轴上方。
然后注意到如果一个半径较小的圆合法，那么半径比他大的圆一定也存在一个合法的位置，于是我们在实数域上二分。设当前二分到的半径为(K)，那么显然圆的纵坐标就是(K)了，设圆的横坐标为(X)。
那么对于一个点(i)，该点在这个圆内当且仅当
稍作变形有
即可得到对于该点来说，半径为(K)的圆合法的(X)对于范围：
然而并不对。注意到(Delta)可以进一步化简：
看起来没什么不同？假的！下面我们就会谈到二分的范围，(K^2)是会爆掉 (Double) 的。
用了 (Long Double) 还是过不了？前面的式子精度会爆炸，精度丢失远高于后面的式子。
(\)
然后二分边界就是对于所有点当前半径的合法区间的交集不为空。
这个部分可以维护最大的 (L) 和最小的 (R) ，直接判断 (R>L) 即可。
当时NC想什么差分数组区间标记前缀和，判断最大权是否为N
(\)
然后讨论二分区间。极限数据两点分布于((-10^7,1))和((10^7,1))，此时半径有(5 imes10^{13})之大！
所以二分上界设的大一点不虚((10^{18})之类的())。
(\)
然后还有一个细节。注意(Delta)计算的时候根号下的部分。
必须保证(2Ky_i-y_i^2ge 0)，也就是(2Kge y_i)，不加这一个特判，负数开根右转自闭......
(\)
(Code)
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define R register
#define gc getchar
#define N 100010
using namespace std;
bool f=0;
const double eps=1e-8;
int n;
struct point{double x,y;}p[N];
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
inline bool valid(double x){
double l=-(double)1e18,r=(double)1e18,dlt;
for(R int i=1;i<=n;++i){
if(p[i].y>x+x) return 0;
dlt=sqrt(p[i].y*(2*x-p[i].y));
l=max(l,p[i].x-dlt); r=min(r,p[i].x+dlt);
}
return (r-l+eps>=0.0);
}
int main(){
n=rd();
for(R int i=1;i<=n;++i){
p[i].x=(double)rd();
p[i].y=(double)rd();
if(p[i].y<0.0) f=1;
}
if(f==1) for(R int i=1;i<=n;++i){
p[i].y=-p[i].y;
if(p[i].y<0.0) {puts("-1");return 0;}
}
int t=0;
R double l=0.0,r=(double)1e18,mid;
while(t<=300){
mid=(l+r)/2.0; ++t;
valid(mid)?r=mid:l=mid;
}
printf("%.10lf",l);
return 0;
}