UVa 10382 Watering Grass （区间覆盖贪心问题+数学）

题意：有一块长为l，宽为w的草地，在其中心线有n个喷水装置，每个装置可喷出以p为中心以r为半径的圆，

选择尽量少的装置，把草地全部润湿。

析：我个去啊，做的真恶心，看起来很简单，实际上有n多个坑啊，首先这个题，应该可以看出来是贪心算法，

具体的说是区间覆盖问题，这个问题总体来说不难，但是在这有了巨多的坑。要注意以下几点：

1.这是一个草坪，不是线段，首先你要先把实验室转化为线段。

2.这个喷水装置喷出是圆，不是矩形，要运用数学知识进行运算。

3.输入的半径的两倍如果小于等于宽度，就得忽略不记。因为你算上也没有作用。

4.这个要用浮点数存，我没考虑精度，好歹也过了，还不算太坑。

这个图片是我从网上截的地址是http://blog.csdn.net/shuangde800/article/details/7828675

这个图片可以帮助理解。剩下的就和普通的区间覆盖没太大区别了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
const int maxn = 10000 + 10;

struct node{
    double l, r;
    node() { }
    node(double ll, double rr) : l(ll), r(rr) { }
    bool operator < (const node &p) const{
        return l < p.l;
    }
};

node a[maxn];

int main(){
//    freopen("in.txt", "r", stdin);
    int n;
    double l, w;
    while(~scanf("%d %lf %lf", &n, &l, &w)){
        int indx = 0;
        double p, r;
        for(int i = 0; i < n; ++i){
            scanf("%lf %lf", &p, &r);
            double x = sqrt(r*r - (w/2.0)*(w/2.0));
            if(2 * r > w)  a[indx++] = node(p-x, p+x);
        }
        sort(a, a+indx);
        double s = 0, e = 0;
        int cnt = 1;
        if(a[0].l > s){  printf("-1
");  continue;  }

        for(int i = 0; i < indx; ++i){
            if(a[i].l <= s)  e = max(e, a[i].r); //寻找最大区间
            else{
                ++cnt; //记数
                s = e; //更新s
                if(a[i].l <= s)  e = max(e, a[i].r);
                else  break; //无解，退出循环
            }
            if(e >= l)  break;   //提前结束
        }

        if(e < l)  printf("-1
");
        else  printf("%d
", cnt);
    }
    return 0;
}