题意
坐标轴中有
n
n
n个点，需要画一个圆，这个人与
x
x
x轴相切，且包含全部的
n
n
n个点，问这个圆的半径最小是多少。
题解
二分搜索半径，观察可以发现，这个圆的圆心一定是在
y
=
R
y = R
y=R上面移动的，所以我们可以依据这个半径确定每个点的圆心在
y
=
R
y=R
y=R这条线上的范围，如果所有的点的圆心的范围有交集，那么这个
R
R
R就是符合条件的。 对于一个点，其可能的圆心范围是
l
=
x
−
R
2
−
(
y
−
R
)
2
,
r
=
l
=
x
+
R
2
−
(
y
−
R
)
2
l = x-\sqrt{R^2-(y-R)^2}, r =l = x+\sqrt{R^2-(y-R)^2}
l=x−R2−(y−R)2
,r=l=x+R2−(y−R)2
，需要判断一下根号下为负数的情况，还有直接
R
∗
R
R*R
R∗R会爆精度，需要化简一下。
代码
#include <iostream>
#include <cmath>
using namespace std
;
const int maxn
= 1e5+5;
const double EPS
= 1e-8;
int n
;
struct Node
{
double x
,y
;
}cor
[maxn
];
bool ok(double x
) {
double l
= -1e10, r
= 1e10;
for(int i
= 0; i
< n
; ++i
) {
double h
= abs(cor
[i
].y
-x
);
if(h
> x
) return 0;
double range
= sqrt(cor
[i
].y
*(2*x
-cor
[i
].y
));
l
= max(l
, cor
[i
].x
-range
), r
= min(r
, cor
[i
].x
+range
);
}
return (r
-l
)>EPS
;
}
int main() {
scanf("%d", &n
);
bool fg1
= false, fg2
= false;
for(int i
= 0; i
< n
; ++i
) {
scanf("%lf%lf", &cor
[i
].x
, &cor
[i
].y
);
if(cor
[i
].y
< 0)
fg1
= true, cor
[i
].y
= -cor
[i
].y
;
else
fg2
= true;
}
if(fg1
&& fg2
) {
puts("-1");
}
else if(n
== 1) {
printf("%lf\n", cor
[0].y
/2);
}
else {
double l
= 0, r
= 1e18, ans
;
for(int i
= 0; i
< 1000; ++i
) {
double mid
= (l
+r
)/2;
if(ok(mid
)) {
r
= mid
;
ans
= mid
;
}
else l
= mid
;
}
printf("%lf\n", ans
);
}
return 0;
}
