UVa-10382 Watering Grass **

/*
 * Uva-10382-Watering Grass.cpp
 *
　　      。。（           ，      WA，，        ，   AC  ，  。。
 *
 *       ： http://apps.hi.baidu.com/share/detail/24628400
 *
 *  Created on: 2011-10-3
 *      Author: 
 */
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxN = 10000 + 5;
const double eps = 1E-7;

int n, l, w;
struct SData{
    double x, y;
};
SData interval[maxN];

//  
inline int lfcmp(double x){
    if (x > -eps) return 1;
    else return -1;
}

// X   
inline int cmp(const void *a,const void *b){
    return lfcmp( (((SData*)a)->x)-(((SData*)b)->x) );
}

//    -  
void greedy(){
    int i = 0, ans = 0, j;
    double cover = 0, tmpMax;
    bool covered = false;
    while(i < n){
        j = i;
        tmpMax = cover;
        while(j<n && lfcmp(cover - (interval[j].x)) > 0){
            if(lfcmp((interval[j].y) - tmpMax) > 0)
                tmpMax = interval[j].y;
            j++;
        }
        if(i == j) break;

        ans++;
        cover = tmpMax;
        i = j;

        if(lfcmp(cover - l) > 0){
            covered = true;
            break;
        }
    }
    if(covered) printf("%d
", ans);
    else printf("-1
");

}


int main(){
    while(scanf("%d %d %d", &n, &l, &w) != EOF){
        int p[maxN], r[maxN];
        for(int i=0; i<n; i++)
            scanf("%d %d", &p[i], &r[i]);

        for(int i=0; i<n; i++){
            //     ，   
            if(r[i] * 2 < w){
                interval[i].x = 0;
                interval[i].y = 0;
                continue;
            }

            double d = sqrt((double)r[i]*r[i] - (double)w*w/4);
            interval[i].x = p[i] - d;
            interval[i].y = p[i] + d;
        }

        qsort(interval, n, sizeof(SData), cmp);

        greedy();
    }

    return 0;
}