Posted on 2008-10-16 15:15
岁月流逝 阅读(184)
评论(0) 编辑 收藏 引用
算法：
1 排序 算出每个岛可安雷达的最左边坐标和最右边坐标 左座标按升序排列 左相同时右按照降序排列
2 贪心选取 更新最右边的坐标 如果下一个的左座标大于当前最右边 数目加一 否则的话更新最右边的值
排序的时候因为是DOUBLE 所以那个qsort还要小小的注意下写法
PS:还有d可能是负数！
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
struct Point
{
double left;
double right;
};
Point a[10000];
int cmp(const void *p1, const void *p2)
{
Point c1 = *(Point *)p1;
Point c2 = *(Point *)p2;
double temp = c1.left - c2.left;
if (temp > 0.0) return 1;
else if (temp < 0.0) return -1;
else {
temp = c2.right - c1.right;
if (temp > 0.0) return 1;
else return -1;
}
}
int main()
{
int n;
int i,j;
int cnt = 1;
double x,y,r,d;
double tmp ;
double dd;
int flag ;
while(scanf("%d%lf",&n,&d)!=EOF)
{
flag = 0;
if(n==0&&d==0)
break;
dd=d*d;
for(i = 0;i<n;i++)
{
scanf("%lf%lf",&x,&y);
r =sqrt(1.0*(dd- y*y));
a[i].left = x-r;
a[i].right= x+r;
if(d<y)
{
flag = 1;
}
}
if(flag)
{
printf("Case %d: %d\n",cnt++,-1);
continue;
}
qsort(a,n,sizeof(a[0]),cmp);
int count = 1;
tmp = a[0].right;
for(i = 1;i<n;i++)
{
if(tmp < a[i].left)
{
count++;
tmp = a[i].right;
}
else
{
if(tmp>a[i].right)
tmp = a[i].right;
}
}
printf("Case %d: %d\n",cnt,count);
cnt++;
}
return 0;
}
Tags -
贪心 ,
排序 ,
雷达 ,
pku
文章来源:
http://www.feng5166.com/blog/read.php?118