首先,直径小于草坪宽度的喷水器不选。
然后,按喷水器能够覆盖草坪的矩形范围 转换成 区间覆盖问题。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <string> #include <stack> #include <cmath> #include <queue> #include <set> #include <map> typedef long long ll; using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e4+5; int n,len,wid; int num; struct water{ double l,r;//区间左右坐标 }; water wa[maxn]; bool cmp(water a,water b){ return a.l<b.l; } int solve(){ double start=0; int i=0,ans=0; while(i<num){ if(wa[i].l >start)return -1; double maxr=-1; while(i<num && wa[i].l<=start ){ maxr=max(maxr,wa[i].r); i++; } start=maxr; ans++; } if(start<len)return -1; return ans; } int main() { while(scanf("%d %d %d",&n,&len,&wid)!=EOF){ int pos,radius; num=0; for(int i=0;i<n;++i){ scanf("%d %d",&pos,&radius); if(2*radius>=wid){ double temp=sqrt( ((double)radius)*radius-((double)wid)*wid/4); //printf("%f ", temp); wa[num].l=pos-temp; wa[num].r=pos+temp; //printf("l==%f r==%f ",wa[num].l,wa[num].r ); num++; } } sort(wa,wa+num,cmp);//按左坐标从小到大排序 int ans=solve(); printf("%d ",ans ); } return 0; }