锐客网

  1. 首页 > it技术 > >

Codeforces-1059D（ Nature Reserve（二分））

思维

D. Nature Reserve
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There is a forest that we model as a plane and liven n n rare animals. Animal numberi i i has its lair in the point( x i , y i ) (x_i,y_i) (xi?,yi?). In order to protect them, a decision to build a nature reserve has been made.
The reserve must have a form of a circle containing all lairs. There is also a straight river flowing through the forest. All animals drink from this river, therefore it must have at least one common point with the reserve. On the other hand, ships constantly sail along the river, so the reserve must not have more than one common point with the river.
For convenience, scientists have made a transformation of coordinates so that the river is defined byy = 0 y=0 y=0. Check whether it is possible to build a reserve, and if possible, find the minimum possible radius of such a reserve.
Input
The first line contains one integern ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1≤n≤105) — the number of animals.
Each of the next n lines contains two integersx i , y i ( ? 1 0 7 ≤ x i , y i ≤ 1 0 7 ) x_i, y_i (?10^7≤x_i,y_i≤10^7) xi?,yi?(?107≤xi?,yi?≤107) — the coordinates of the i-th animal’s lair. It is guaranteed that yi≠0. No two lairs coincide.
Output
If the reserve cannot be built, print ?1. Otherwise print the minimum radius. Your answer will be accepted if absolute or relative error does not exceed1 0 ? 6 10^{?6} 10?6.
Formally, let your answer be a, and the jury’s answer be b. Your answer is considered correct if∣ a ? b ∣ m a x ( 1 , ∣ b ∣ ) ≤ 1 0 ? 6 \frac{|a?b|}{max(1,|b|)}≤10^{?6} max(1,∣b∣)∣a?b∣?≤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
Note
In the first sample it is optimal to build the reserve with the radius equal to 0.5
and the center in (0, 0.5).
In the second sample it is impossible to build a reserve.
In the third sample it is optimal to build the reserve with the radius equal to 58
and the center in( 1 2 , 5 8 ) (\frac12,\frac58) (21?,85?).
思路：容易想到二分半径R，如何检查是否存在一个半径为R的圆能够包含所有的点且与x轴相切呢？
很明显那个圆的圆心在直线y=R上。
那么对于每个点 ( x i , y i ) (x_i,y_i) (xi?,yi?)来说，以 ( x i , y i ) (x_i,y_i) (xi?,yi?)为圆心，R为半径作一个圆 C i C_i Ci?，那么 C i C_i Ci?截直线y=R的那条线段，圆心处在这条线段上才是符合条件的。
那么对于所有点，判断他们与直线y=R的截线段是否有公共点即可。

#include using namespace std; const int MAX=1e5+10; const int MOD=1e9+7; const double PI=acos(-1.0); typedef long long ll; struct Point { double x,y; }p[MAX]; int n; int cal(double y) { double l=-1e18,r=1e18; for(int i=0; i【Codeforces-1059D（ Nature Reserve（二分））】>n; for(int i=0; i0)tag|=1; if(p[i].y<0)tag|=2; p[i].y=fabs(p[i].y); } if(tag==3){puts("-1"); return 0; } double l=0,r=1e18,ans=0; for(int i=1; i<=500; i++) { double m=(l+r)/2; if(cal(m))ans=r=m; else l=m; } printf("%.10f\n",ans); return 0; }

    推荐阅读


    上一篇：时间戳与本地时间转换关系

    下一篇：法国·轻幻想