题意 问最少可用几个圆覆盖矩形区域。
解析 将圆形转换成矩形有效区域，直径小于等于宽度的圆不考虑，从而转化成区间覆盖问题，然后贪心出最少圆。
贪心思想 每次选择出区域左界比上次选出的区域右界小的且区域最长的。更新还未覆盖的区域。
AC 代码
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<algorithm> #define maxn 10010 using namespace std; struct node { double left; double right; } a[maxn]; bool cmp(node a,node b) { return a.left<b.left; } int n; double l,w; int main() { int i,j,k; while(scanf("%d %lf %lf",&n,&l,&w)!=EOF) { int len=0; double p,r; for(i=0; i<n; i++) { scanf("%lf%lf",&p,&r); if(2*r<=w) continue; double k=sqrt(r*r-w*w/4.0); a[len].right=p+k; a[len].left=p-k; len++; } sort(a,a+len,cmp); int sum=0; double le=0,ri=0; int flag=0; if(a[0].left<=0) { int i=0; while(i<len) { int j=i; while(le>=a[j].left&&j<len) { if(a[j].right>ri) ri=a[j].right; j++; } if(i==j) break; sum++; le=ri; i=j; if(ri>=l) { flag=1; break; } } } if(flag) printf("%d ",sum); else printf("-1 "); } return 0; }