首页 > 代码库 > 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