首页 > 代码库 > HDU 4562 守护雅典娜
HDU 4562 守护雅典娜
题目链接: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()); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。