学步园

Problem E
Watering Grass
Input: standard input
Output: standard output
Time Limit: 3 seconds

n sprinklers are installed in a horizontal strip of grass l meters long and w meters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from
the left end of the center line and its radius of operation.

What is the minimum number of sprinklers to turn on in order to water the entire strip of grass?

Input

Input consists of a number of cases. The first line for each case contains integer numbers n, l and w with n <= 10000. The next n lines contain two integers giving the position of a sprinkler and its radius of
operation. (The picture above illustrates the first case from the sample input.)

Output

For each test case output the minimum number of sprinklers needed to water the entire strip of grass. If it is impossible to water the entire strip output -1.

Sample input

8 20 2

5 3

4 1

1 2

7 2

10 2

13 3

16 2

19 4

3 10 1

3 5

9 3

6 1

3 10 1

5 3

1 1

9 1

Sample Output

6

2

-1

(Regionals 2002 Warm-up Contest, Problem setter: Piotr Rudnicku)

题目大意：告诉你洒水车的个数以及草坪的长宽，以及各个洒水车的范围（圆心位置和半径），问你至少需要多少洒水车才能覆盖全草坪？如果都不能，输出 -1

解题思路：先预处理将2维转化为1维的直线，求出每条线段的范围，也就是至少几条线段能覆盖全部，利用贪心的思想，按照起点排序，如果覆盖就尽量覆盖的远一点。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn=10010;
const double eps=1e-7;
int n,len,w;

struct radi{
    double lpos,rpos;
    int pos,r;
    friend bool operator < (radi r1,radi r2){
        return r1.lpos<r2.lpos;
    }
}ra[maxn];


void computing(){
    for(int i=0;i<n;i++){
        if(2*ra[i].r<=w){
            ra[i].lpos=len+100;
            ra[i].rpos=len+100;
            ra[i].pos=len+100;
        }else{
            double range=sqrt((double)ra[i].r*ra[i].r-(double)w*w/4.0);
            ra[i].lpos=ra[i].pos-range;
            ra[i].rpos=ra[i].pos+range;
        }
    }
    sort(ra,ra+n);
    int ans=0;
    double range,pos=0;
    bool flag=true;
    int s=0,i=0;
    while(pos<len){
        range=-1;
        for(i=s;(ra[i].lpos<pos||abs(ra[i].lpos-pos)<eps) && i<n;i++){
            if(ra[i].rpos>range) range=ra[i].rpos;
        }
        if(abs(range+1)<eps){
            flag=false;
            break;
        }
        pos=range;
        s=i;
        ans++;
    }
    if(flag) cout<<ans<<endl;
    else cout<<"-1"<<endl;
}

int main(){
    while(scanf("%d%d%d",&n,&len,&w)!=EOF){
        for(int i=0;i<n;i++) scanf("%d%d",&ra[i].pos,&ra[i].r);
        computing();
    }
    return 0;
}