题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=85904#problem/E
题意：
给定一条草坪，草坪上有ｎ个喷水装置。草坪长ｌ米宽ｗ米，ｎ个装置都有每个装置的位置和喷水半径。要求出最少需要几个喷水装置才能喷满草坪。喷水装置都是装在草坪中间一条水平线上的。
案例：
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
分析：
区间覆盖问题
用贪心，按覆盖最远的排序，每次找最远的然后更行左边界。
这题有个要注意的地方是圆型覆盖，所以在初始化时把其化成矩形覆盖问题，（根据勾股定理转化）
#include<iostream> #include<cstdio> #include<cstring> #include <algorithm> #include<cmath> using namespace std; #define maxn 10100 int n,k; double m,w,x,y; struct node { double l; double r; }a[maxn]; int cmp( node a, node b) //按覆盖最远的排序（半径由大到小） { return a.r > b.r; } int main() { while(scanf("%d%lf%lf",&n,&m,&w)!=EOF) { double L=0; k=0; int i=0,j=0; double d; while(n--) { scanf("%lf%lf",&x,&y); d=sqrt(y*y-(w*w)/4); //转化为矩形覆盖 a[j].l=x-d; a[j++].r=x+d; } sort(a,a+j,cmp); while(L<m) { int i; for(i=0;i<j;i++) { if(a[i].l<=L&&a[i].r>L) { L=a[i].r; k++; break; } } if(i==j) break; } if(L<m) cout<<"-1"<<endl; else cout<<k<<endl; } return 0; }