POJ 1328 Radar Installationon

1.原题

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

2.题意

就是说在坐标轴上给你n个点（y >= 0），然后有半径为M的圆，且圆心都在x轴上，问你至少多少个圆可以包括所有的左边

3.思路

就是先把所有的N个点所可以对应的在x轴上的坐标区间求出来，然后再用sort将x从小到大排列，然后再从0到N-1，现设start为第一个点的y（即区间右边），然后在判断下一个点，如果下一个点的y小于start，则说明这个区间包含在前一个区间中，再将start设置成这个点的y，如果下一个点的x（区间左边）大于start，则这个区间与上一个区间没有交集，则可以将圆的个数加一，然后再将start设置成这个点的y。只是有交集的情况可以直接过滤到，因为对变量没有影响。

4.代码

   
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

struct island
{
    double x;
    double y;
};

island is[1010];
int islandNum = 0;

int operator < (const island& a,const island& b){
    return a.x < b.x;
}

int main(){

    
    int distance = 0;
    int pp = 1;
    while(cin>>islandNum>>distance && (islandNum != 0 || distance != 0)){
        double maxNum = 0.0;
        for (int i = 0;i < islandNum;i++){
            cin>>is[i].x>>is[i].y;
            maxNum = max(maxNum,is[i].y);
        }
        if(maxNum > distance) {
            cout<<"Case "<<pp++<<": -1"<<endl;
            continue;
        }
        for (int i = 0;i < islandNum;i++) {
            double d = sqrt(distance * distance - is[i].y * is[i].y);
            double temp = is[i].x;
            is[i].x = temp - d;
            is[i].y = temp + d;
        }
        sort(is,is+islandNum);
        int circleNum = 1;
        double start = is[0].y;
        for (int i = 1;i < islandNum;i++) {
            if(is[i].y < start) start = is[i].y;
            else if(start < is[i].x) {
                start = is[i].y;
                circleNum++;
            }
        }
        cout<<"Case "<<pp++<<": "<<circleNum<<endl;
    }

    return 0;
}