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){ 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 ; }