首页 > 代码库 > poj1328 Radar Installation 区间贪心
poj1328 Radar Installation 区间贪心
题目大意：
在X轴选择尽量少的点作为圆心，作半径为d的圆。使得这些圆能覆盖所有的点。
思路：
把每个点都转化到X轴上。也就是可以覆盖这个点的圆心的位置的范围[a,b]。然后按照每个点对应的a从小到大排序。第一点需要特殊处理，我们赋值r=b0 。也就是使得第一个圆的圆心的横坐标尽量大。然后遍历剩下的点。对于i点，如果该点的ai大于r, 就需要增加一个圆，圆心为bi ；否则的话，把r更新为r与bi中小的值。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 const int N = 1010; 9 struct node10 {11 double x,y;12 double a,b;13 }p[N];14 bool cmp(node n1,node n2)15 {16 return n1.a<n2.a;17 }18 int main()19 {20 //freopen("test.txt","r",stdin);21 int n,d,ca=1;22 while(scanf("%d%d",&n,&d)!=EOF&&n)23 {24 int i;25 bool flag=0;26 for(i=0;i<n;i++)27 {28 scanf("%lf%lf",&p[i].x,&p[i].y);29 if(p[i].y>d) flag=1;30 }31 printf("Case %d: ",ca++);32 if(flag) printf("-1\n");33 else34 {35 for(i=0;i<n;i++)36 {37 double x=p[i].x,y=p[i].y;38 p[i].a=-sqrt(d*d-y*y)+x;39 p[i].b=sqrt(d*d-y*y)+x;40 }41 sort(p,p+n,cmp);42 double r=p[0].b;43 int ans=1;44 for(i=1;i<n;i++)45 {46 if(p[i].a>r){47 r=p[i].b;48 ans++;49 }50 if(p[i].b<r) r=p[i].b;51 }52 printf("%d\n",ans);53 }54 }55 return 0;56 }
poj1328 Radar Installation 区间贪心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。