CodeForces - 1059D

题目大意：

平面上有n个点，现在需要找这么一个圆，它与y=0相切，且这n个点都在圆上或圆内，求这个圆的最小半径Input输入n，1 <= n <= 10^5
接下来n行，每行表示一个点的坐标，依次是x,y，坐标都是整数且绝对值不超过10^7，同时不存在y=0的点Output这样的圆如果不存在，输出-1，存在则输出其最小半径，误差小于10^-6视为正确，即你的输出可以与样例不同，只要误差在范围内即可
Examples
Input
1
0 1
Output
0.5
Input
3
0 1
0 2
0 -3
Output
-1
Input
2
0 1
1 1
Output
0.625
NoteIn the first sample it is optimal to build the circle with the radius equal to 0.5 and the center in (0, 0.5).

思路：
由于圆和x横坐标相切，因此所有点必须在x轴得一侧，否则圆势必穿过x轴。
已只圆于x轴相切，即$y=r$，根据圆的公式：

其中$(x_i,y_i)$为任意一点坐标。这样就能求出以$(x,r)$为圆心的圆要想包含第i个点的最小半径(即第i个点在圆周上)。遍历一遍所有点，即可求出圆心x轴值已知的情况下，圆要想包含所有点的最小半径。
如果r对x求导，得：

由于$y_i$是同号的，所以$r_x$是单调的。令$r_x=0$，得$x=-x_i$，因此在$x<-x_i$时， $r$单调递减，$x>-x_i$时，$r$单调递增。$r$先增后减，必有最小值，并且呈U形，那么我们可以取Left为-inf，Right为+inf，将区间不断逼近谷底即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const double eps = 1e-8;
int n;
double getRidux(long double x) {
	long double r = 0;
	for (int i = 0; i < n; i++){
		r = max(r, (x - points[i].x) * (x - points[i].x) / points[i].y / 2 + points[i].y / 2);
	}
	return r;
}

int main(){

	cin >> n;
	int hasNeg = 0;

	for (int i = 0; i < n; i++){
		scanf("%lf%lf", &points[i].x, &points[i].y);
		if (points[i].y > 0) {
			hasNeg |= 1;
		}
		if (points[i].y < 0) {
			hasNeg |= 2;
		}
		points[i].y = fabs(points[i].y);
	}

	if (hasNeg == 3) {
		puts("-1");
		return 0;
	}

	long double 
		Left = -1e7,
		Right = 1e7, 
		LeftX,
		RightX, 
		DividSector;

	while (Right - Left > eps){
	        //除的数只要大于2就行，越接近2越快，不过可能注意精度问题。
	        //三分法一般除3，但实际上除2.x会更快
	        //等于2得话LeftX和RightX就相等了，那就不是区间逼近了，第一次就区间变点了。。。
		DividSector = (Right - Left) / 2.000001;
		LeftX = Left + DividSector;
		RightX = Right - DividSector;
		if (getRidux(LeftX) - getRidux(RightX) < 0) {
			Right = RightX;
		}
		else {
			Left = LeftX;
		}
	}
	printf("%lf\n", getRidux(Right));
	return 0;
}