Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 50843 | Accepted: 11415 |
Description
Input
Output
Sample Input
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
Sample Output
Case 1: 2 Case 2: 1
思路:该题题意是为了求出能够覆盖所有岛屿的最小雷达数目,每个小岛对应x轴上的一个区间,在这个区间内的任何一个点放置雷达,则可以覆盖该小岛,区间范围的计算用[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)];这样,问题即转化为已知一定数量的区间,求最小数量的点,使得每个区间内斗至少存在一个点。每次迭代对于第一个区间, 选择最右边一个点, 因为它可以让较多区间得到满足, 如果不选择第一个区间最右一个点(选择前面的点), 那么把它换成最右的点之后, 以前得到满足的区间, 现在仍然得到满足, 所以第一个区间的最右一个点为贪婪选择, 选择该点之后, 将得到满足的区间删掉, 进行下一步迭代, 直到结束。
以左区间为准:
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> using namespace std; const int M = 1000 + 5; double x, y; double dis; //圆的半径 double temp; int ans; //用于统计结果 int n; //点的个数 int flag; //用于判断 struct node { double left; //左区间 double right; //右区间 } island[M]; bool cmp(node a, node b) //按左区间从小到大排序 { return a.left<b.left; } int main() { int cas=0; while(scanf("%d%lf", &n, &dis) && n && dis) { flag=0; ans=0; cas++; for(int i=0; i<n; i++) { scanf("%lf%lf", &x, &y); if(y>dis||y<0) //不符合的点 flag=1; island[i].right = x+sqrt(dis*dis-y*y); island[i].left = x-sqrt(dis*dis-y*y); } if(flag==1) printf("Case %d: -1\n",cas); else { sort(island, island+n, cmp); //sort排序 temp = island[0].right; ans=1; for(int i=1; i<n; i++) { if(island[i].right<temp) //说明这个区间被上个区间所包含,只要小区间满足的点,大区间肯定也满足 temp=island[i].right; else if(island[i].left>temp) //说明这两个区间没有重合部分,也就不能用一个圆表示,则结果加一 { ans++; temp=island[i].right; } } printf("Case %d: %d\n", cas, ans); } } return 0; }
一右区间为准:(这是我同学写的右区间)
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; struct node { double a,b; }s[1005],l[1005]; int cmp(node x,node y) { return x.b<y.b; } int main() { int n,m,k=0; while(cin>>n>>m) { if(n==0&&m==0) break; int i,j,p=0; for(i=0;i<n;i++) { scanf("%lf%lf",&s[i].a,&s[i].b); if(s[i].b<0||s[i].b>m) p=1; l[i].a=s[i].a-sqrt(m*m-s[i].b*s[i].b); l[i].b=s[i].a+sqrt(m*m-s[i].b*s[i].b); } sort(l,l+n,cmp); int sum=1; double r=l[0].b; for(i=1;i<n;i++) { if(l[i].a>r) { r=l[i].b; sum++; } } printf("Case %d: ",++k); if(p) cout<<-1<<endl; else cout<<sum<<endl; } return 0; }
POJ 1328:Radar Installation,布布扣,bubuko.com
原文:http://blog.csdn.net/u013487051/article/details/37569807