Posted on 2008-10-16 15:15
歲月流逝 閱讀(194)
評論(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