算法：
1 排序 算出每個島可安雷達的最左邊坐標和最右邊坐標 左座標按升序排列 左相同時右按照降序排列
2 貪心選取 更新最右邊的坐標 如果下一個的左座標大于當前最右邊 數目加一 否則的話更新最右邊的值
排序的時候因為是DOUBLE 所以那個qsort還要小小的注意下寫法
代碼如下
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct Point
{
double left;
double right;
}points;
int cmp(const void *p1, const void *p2)
{
Point I1 = *(Point *)p1;
Point I2 = *(Point *)p2;
double temp = I1.left - I2.left;
if (temp > 0.0) return 1;
else if (temp < 0.0) return -1;
else {
temp = I2.right - I1.right;
if (temp > 0.0) return 1;
else return -1;
}
}
int main()
{
Point points[1005];
int n,d,x[1005],y[1005],i,dd,cnt,flag;
int t=0;
double sqrtdy,right;
while(scanf("%d%d",&n,&d)&&!(n==0&&d==0))
{
t++;
flag=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&x[i],&y[i]);
if(y[i]>d) flag=1;
}
if(flag)
{
printf("Case %d: %d\n",t, -1);
continue;
}
dd=d*d;
for (i = 0; i < n; i++)
{
sqrtdy = sqrt(dd - y[i]*y[i]);
points[i].left = x[i]-sqrtdy;
points[i].right =x[i]+ sqrtdy;
}
qsort(points,n,sizeof(Point),cmp);
for(i=0;i<n;i++)
{
printf("%d %d\n",points[i].left,points[i].right);
}
cnt=1;
right=points[0].right;
for(i=1;i<n;i++)
{
if(points[i].left>right)
{
cnt++;
right=points[i].right;
}
else {
if (points[i].right < right)
right = points[i].right;
}
}
printf("Case %d: %d\n",t,cnt);
}
}