Poj 1328 / OpenJudge 1328 Radar Installation

1.Link：

http://bailian.openjudge.cn/practice/1328/

2.Content：

Radar Installation

Time Limit: 1000MS Memory Limit: 10000K

Total Submissions: 52833 Accepted: 11891

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

Figure A Sample Input of Radar Installations

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input
3 2
1 2
-3 1
2 1

1 2
0 2

0 0
Sample Output
Case 1: 2
Case 2: 1
Source

Beijing 2002

3.Method：

（1）求出每个岛能够安装灯塔的区域，用结构体表示Lines

（2）根据最右快排，这里要尤其注意double类型的compare怎么写

（3）贪心算法求最小灯塔数量

4.Code：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

struct LINE
{
    double l;
    double r;
};

int cmp(const void *a,const void *b)
{
   LINE line1 = *((LINE *)a);
   LINE line2 = *((LINE *)b);
   /*if(line1.r == line2.r)
   {
       if(line1.l == line2.l) return 0;
       return line1.l > line2.l ? 1 : -1;
   }
   else return line1.r > line2.r ? 1 : -1;*/
   if(line1.r == line2.r) return 0;
   else return line1.r > line2.r ? 1 : -1;
}

int main()
{
   //freopen("D://input.txt", "r", stdin);

   int i;

   int n,d;
   int count = 1;
   int x,y;
   int flag;
   double ins;

   cin >> n >> d;
   while(n!= 0 || d != 0)
   {

       LINE *lines = new LINE[n];

       flag = 1;
       for(i = 0; i < n; ++i)
       {
           cin>>x>>y;
           if(d < y) flag = 0;
           else
           {
               ins = sqrt(d * d - y * y);
               lines[i].l = x - ins;
               lines[i].r = x + ins;
           }
       }

       if(flag == 0) cout<<"Case "<< (count++) <<": -1"<<endl;
       else
       {
           qsort(lines,n,sizeof(LINE),cmp);

           /*for(i = 0; i < n; ++i)
           {
               cout << lines[i].l << " " << lines[i].r << endl;
           }*/

           int num = 1;
           double max_r = lines[0].r;
           for(i = 1; i < n; ++i)
           {
               if(max_r < lines[i].l)
               {
                   num++;
                   max_r = lines[i].r;
               }
           }
           cout << "Case " << (count++) << ": " << num <<endl;
       }

       delete [] lines;

       cin >> n >> d;
   }

   //fclose(stdin);
   return 0;
}

5：Reference：

http://blog.sina.com.cn/s/blog_48f85e1d0100nslz.html

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 52833		Accepted: 11891