首页 > 代码库 > HDU 4562 守护雅典娜

HDU 4562 守护雅典娜

2024-07-09 00:07:18   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4562

题意：给出一个点p(X,Y)以及若干圆。从中选出尽可能多的圆满足：圆能且只能包含p或者原点中的一个（不能在圆上）；圆之间不能相交或者相切。

思路：首先分理出只包含原点或者p的圆，然 后分别按照半径升序排序。分别对包含原点和p的进行dp。f1[i]表示包含原点的圆中前i个最多选出多少个。f2[i]表示p的。然后合并。就是枚举 f1的i和f2的j，若这两个圆不冲突，那么就能选出f1[i]+f2[j]个。

 

const int N=1005;class point{    public:    int x,y;    point(){}    point(int _x,int _y)    {        x=_x;        y=_y;    }    void get()    {        RD(x,y);    }    point operator-(point a)    {        return point(x-a.x,y-a.y);    }    int len()    {        return x*x+y*y;    }};class Circle{    public:    point p;    int R;    void get()    {        p.get();        RD(R);    }    int on(point a)    {        return R*R==(a-p).len();    }    int in(point a)    {        return R*R>(a-p).len();    }    int ok(Circle a)    {        int x=abs(a.R-R),y=a.R+R,L=(a.p-p).len();        return L<x*x||L>y*y;    }};point a,b;vector<Circle> p,q;int n,f1[N],f2[N];int cmp(Circle a,Circle b){    return a.R<b.R;}int DP(){    sort(p.begin(),p.end(),cmp);    sort(q.begin(),q.end(),cmp);    int ans=0,i,j;    FOR0(i,SZ(p))    {        f1[i]=0;        FOR0(j,i) if(p[i].ok(p[j])) f1[i]=max(f1[i],f1[j]);        f1[i]++;        ans=max(ans,f1[i]);    }    FOR0(i,SZ(q))    {        f2[i]=0;        FOR0(j,i) if(q[i].ok(q[j])) f2[i]=max(f2[i],f2[j]);        f2[i]++;        ans=max(ans,f2[i]);    }    FOR0(i,SZ(p)) FOR0(j,SZ(q)) if(p[i].ok(q[j]))    {        ans=max(ans,f1[i]+f2[j]);    }    return ans;}int main(){    int num=0;    rush()    {        RD(n); b.get();        a=point(0,0);        Circle t;        int i;        p.clear(); q.clear();        FOR0(i,n)        {            t.get();            if(t.on(a)||t.on(b)) continue;            if(t.in(a)&&!t.in(b)) p.pb(t);            if(!t.in(a)&&t.in(b)) q.pb(t);        }        printf("Case %d: ",++num);        PR(DP());    }}

 

 

 


联系
我们