首页 > 代码库 > bzoj1946: [Ceoi2006]ANTENNA
bzoj1946: [Ceoi2006]ANTENNA
给出N个点的坐标,要求能够覆盖其中至少K个点的圆的最小半径及圆心位置。
最优答案圆周上一定有点,枚举这个点,二分半径扫描线判定,随机打乱输入顺序并加上最优性剪枝,由于答案期望变优$O(logn)$次,期望时间复杂度为$O(n^2logn+nlognlog(\frac{MaxAns}{eps}))$
#include<bits/stdc++.h>const double pi=acos(-1);int n,k;struct pos{ int x,y; double a,d; void cal(){ a=atan2(y,x); d=sqrt(x*x+y*y); } pos operator-(pos w)const{return (pos){x-w.x,y-w.y};} bool operator<(pos w)const{return a<w.a;}}ps[555],as[555],p0;int ap;double ans=20000,ax=5000,ay=5000;struct ev{ double a; int t; bool operator<(ev w)const{return a<w.a;}}e[1111];void upd(double r,double a){ if(r<ans){ ans=r; ax=p0.x+cos(a)*r; ay=p0.y+sin(a)*r; }}bool chk(double R){ double R2=R*2; int ep=0,s=0; for(int i=0;i<ap;++i)if(as[i].d<=R2){ double b=acos(as[i].d/R2),l=as[i].a-b,r=as[i].a+b; if(l<-pi)l+=pi*2; if(r>pi)r-=pi*2; s+=l>r; e[ep++]=(ev){l,1}; e[ep++]=(ev){r,-1}; } if(s>=k){ upd(R,-pi); return 1; } std::sort(e,e+ep); for(int i=0;i<ep;++i)if((s+=e[i].t)>=k){ upd(R,e[i].a); return 1; } return 0;}int main(){ scanf("%d%d",&n,&k); --k; for(int i=0,x,y;i<n;++i){ scanf("%d%d",&x,&y); ps[i]=(pos){x,y}; } std::random_shuffle(ps,ps+n); for(int i=0;i<n;++i){ ap=0; p0=ps[i]; for(int j=0;j<n;++j){ as[j]=ps[j]-p0; as[j].cal(); if(as[j].x|as[j].y)as[ap++]=as[j]; } std::sort(as,as+ap); double L=0,R=ans,M=ans-5e-9; while(R-L>1e-8){ if(chk(M))R=M; else L=M; M=L+(R-L)/2; } } printf("%.6f\n%.6f %.6f",ans,ax,ay); return 0;}
bzoj1946: [Ceoi2006]ANTENNA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。