【数学|CF 514D.Nature Reserve 几何,二分,交集】题意:二维平面上n个点(x[i],y[i]) 问是否能找到一个和x轴相切的圆.并且这个圆包含n个点.
n<=1e5,-1e7<=x[i],y[i]<=1e7. 求出满足条件的圆中,半径最小为多少?
若n个点都在x轴以上或者x轴以下,显然有解,并且R有单调性.(若(x,y,R)为一解,那么(x,y+1,R+1)肯定也有解).
二分半径R,设圆心为(X,Y) 若圆和x轴相切,则 Y=R
若确定圆心的横坐标X,则确定该圆并判断n个点是否落在圆内. 但是X可以为小数,范围又大.无法确定.
从每个点的角度去考虑,因为确定了半径和Y. 一个点(x[i],y[i]) 距离它的(X,Y)最多为R,(X-x[i])^2 +(R-y[i])^2 = R^2.
则可选的X范围在[x1,x2]这个区间内. 那么看n个X的可选区间是否有交集即可.
#include
using namespace std;
typedef long double ld;
const int N=2e5+5;
const ld eps=1e-8;
int n;
ld x[N],y[N];
bool check(ld R){
//(X-x[i])^2 = R^2 - (R-y[i])^2;
ld l=-1e18,r=1e18;
for(int i=1;
i<=n;
i++){
ld A=1,B=-2*x[i],C=x[i]*x[i]-2*R*y[i]+y[i]*y[i];
ld delta=B*B-4*A*C;
if(delta<0) return false;
ld x1=(-B+sqrt(delta))/2.0;
ld x2=(-B-sqrt(delta))/2.0;
if(x1eps;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;
i<=n;
i++) cin>>x[i]>>y[i];
int cnt=0,flag=0;
for(int i=1;
i<=n;
i++) if(y[i]<0) cnt++;
if(cnt==0||cnt==n) flag=true;
if(!flag){
cout<<-1<<'\n';
return 0;
}
if(cnt==n) for(int i=1;
i<=n;
i++) y[i]=-y[i];
ld l=0,r=1e18,res=-1;
for(int i=0;
i<500;
i++){
ld m=(l+r)/2.0;
if(check(m)) r=m,res=m;
else l=m;
}
cout<
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- AIoT(人工智能+物联网)|程序员的数学【线性代数基础】
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- topcoder|Topcoder SRM 661 Div1 Easy: MissingLCM
- HDU 5184 Brackets (卡特兰数)
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率