uva10382

题意：有一块草坪，长为l，宽为w，在其中心线的不同位置处装有n个点状的喷水装置，每个装置i可以将以它为中心，半径为ri的圆形区域润湿，清选择尽量少的喷水装置，把整个草坪全部润湿。
分析：其实是一个最小区间覆盖的问题，用最少的区间覆盖给定的区间。

代码：

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int MAXN = 11111;
double l, w;
pair<double, double>a[MAXN];
int main(){
        int n;
        while(scanf("%d%lf%lf", &n, &l, &w)!=EOF){
                int i,j,m=0;
                for(i=0; i<n; i++){
                        double x, r;
                        scanf("%lf%lf", &x, &r);
                        if(w>=2*r) continue;
                        double tmp=sqrt(r*r-w*w/4);
                        a[m++]=make_pair(x-tmp,x+tmp);
                }
                sort(a,a+m);
                int cnt=0;
                bool flag=false;
                double low=0, up=0;
                for(i=0; i<m; i++){
                        if(a[i].first>up) break;
                        if(a[i].second>up){
                                for(j=i; j<m&&a[j].first<=low;j++)
                                        if(up<a[j].second) up=a[j].second;
                                cnt++;
                                if(up>=l){flag=true;break;}
                                low=up;
                        }
                }
                if(flag) printf("%d\n", cnt);
                else puts("-1");
        }
        return 0;
}