原题: http://acm.nyist.net/JudgeOnline/problem.php?pid=12
//区间覆盖问题 //跟喷水装置(一)类似，通过装置的半径和位置计算出他的有效喷水区间 //在区间相交时还要选择终点最远的那个 #include<iostream> #include<cstdio> #include<algorithm> #include<math.h> using namespace std; struct R { double bi; double ei; }r[10001]; int cmp(const void*aa,const void*bb) { R a=*(R*)aa; R b=*(R*)bb; if(a.bi!=b.bi)return a.bi>b.bi;//按开始由小到大. return a.ei<b.ei;//开始相同,按结束由大到小 } int main() { int t; scanf("%d",&t); while(t--) { int n; double w,h; double x,a; int pos=0; scanf("%d %lf %lf",&n,&w,&h); for(int i=0;i<n;i++) { scanf("%lf %lf",&x,&a); if(a>=h/2) { r[pos].bi=x-sqrt(a*a-h*h/4); r[pos].ei=x+sqrt(a*a-h*h/4); pos++; } } qsort(r,pos,sizeof(r[0]),cmp); double ei=0; int cnt=0; while(true) { int pos=-1; double tmp=0; for(int i=0;i<n;i++) { if(r[i].bi==-1)continue; if(r[i].bi>ei)break; if(r[i].bi<=ei && r[i].ei>tmp)//找相交而且结束最远的 { pos=i; tmp=r[i].ei; } } if(pos==-1){ break; }else{ ei=r[pos].ei; cnt++; r[pos].bi=-1; if(ei>=w)break; } } if(ei>=w) { printf("%d\n",cnt); }else{ printf("0\n"); } } return 0; }