锐客网

  1. 首页 > it技术 > >

数学|CF 514D.Nature Reserve 几何,二分,交集

数学codeforces计算几何------泛做

【数学|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<




    推荐阅读


    上一篇：ELF，PE文件格式 及 延迟绑定（PLT、GOT表）、动态链接（.dynamic段）

    下一篇：wpf——自定义进度条控件