算法学习之路|区间选点问题-白红宇

一条海岸线，在海中有一些岛屿，要在岸上建一些雷达，每个雷达有一定的照射范围d，问至少要建造多少雷达才能覆盖所有岛屿

输入格式：

输入有多组数据，第一行d,n为雷达半径和海岛个数，接下来n行每行两个数，是每个岛屿坐标，输入0 0结束

输出格式：

输出雷达个数，无法覆盖就输出-1

输入样例：

3 2

1 2

-3 1

2 1

1 2

0 2

0 0

输出样例：

Case 1: 2

Case 2: 1

解题思路：把覆盖范围区间化，简化成区间选点问题，贪心，

思路不难，但是有一些坑。

#include
    
       #include
     
        #include
      
          struct island  {      float left,right;  }is[1010];  int cmp(const void *a, const void *b)  {      return (*(struct island*)a).left>(*(struct island*)b).left?1:-1;  }  int main()  {      int n,d,num =1;      while(scanf("%d%d",&n,&d)!=EOF&&(n||d))      {          int x,y,flag=0;          for(int i=1;i<=n;i++)          {              scanf("%d%d",&x,&y);              if(y>d)              flag=1;              float dis;              dis=sqrt((float)(d*d-y*y));              is[i].left=(float)x-dis;              is[i].right=(float)x+dis;          }          qsort(is+1,n,sizeof(is[0]),cmp);          int sum=1;          float r;          r=is[1].right;          for(int i=2;i<=n;i++)          {              if(r>is[i].right)            r=is[i].right;              else if(is[i].left>r)             {                  sum++;                  r=is[i].right;              }          }          if(flag)          printf("Case %d: -1\n",num++);          else          printf("Case %d: %d\n",num++,sum);      }      return 0;  }