Radar Installation
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
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 InstallationsInput
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
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
代码 ：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define M 1010
using namespace std ;
struct node { double s , e ; } qe[M] ;
bool vi[M] ;
double ab( double h , double y ){
return sqrt( h * h - y * y ) ;
}
double ma( double a , double b ){
if( a > b ) return a ;
return b ;
}
int cmp( node a , node b ){
return a.e < b.e ;
}
int main()
{
int i , j , n ,sum , k = 0 ;
double u , v , m , max ;
while(scanf( "%d%lf" , &n , &m ) != EOF ){
if( n == 0 && m == 0.0 ) break ;
max = 0.0 ;k++ ;
memset( vi , 0 , sizeof(vi) ) ;
for( i = 1 ;i <= n ;i++){
scanf( "%lf%lf" , &u , &v ) ;
qe[i].s = u - ab( m , v ) ;
qe[i].e = u + ab( m , v ) ; // 把在能覆盖改点的左右端点 求出
max = ma( v , max ) ;
}
printf( "Case %d: " , k ) ;
if( max > m ) cout << "-1" << endl ; // 如果 最远的 不能覆盖 就无解
else {
sort( qe + 1 , qe + n + 1 , cmp ) ; // 按右端点从小到大排序
for( i = 1 ;i <= n ;i++)
for( j = i + 1 ; j <= n ;j++){
if(qe[i].s >= qe[j].s ) // 如果被覆盖就不考虑
vi[j] = 1 ;
}
// for( i = 1 ;i <= n ;i++)
// printf( "%.2lf %.2lf\n" , qe[i].s , qe[i].e ) ;
sum = 0 ;
for( i = 1 ;i <= n ;i++)
if(vi[i] == 0 ){
max = qe[i].e ;
sum++ ;
for( j = i + 1 ; j <= n ;j++){
if( qe[j].s <= max ) vi[j] = 1 ; // 覆盖
else break ;
}
}
cout << sum << endl ;
}
}
}