题目大意:在二维坐标系上y=k是分界线,y>k的部分是n个敌人,y<k的部分要安置T个狙击手。每个狙击手的射程是D。问安置好这些狙击手之后,在能将所有的敌人都打掉的情况下最大化狙击手到y=k的距离。
思路:二分答案。然后确定每个敌人可被攻击到的x的区间范围,然后对这些区间做区间覆盖统计需要安狙击手的个数。
struct pp{ ll x,y; }pnt[maxn]; struct ppt{ ll st,ed; }axis[maxm]; bool cmp(ppt a,ppt b){ return a.ed<b.ed; } ll k,n,s,d; bool calc(ll mid){ memset(axis,0,sizeof(axis)); for(ll i=0;i<n;i++){ if(pnt[i].y+mid>d)return false; ll tmp=(ll)(sqrt(d*d*1.0-1.0*(pnt[i].y+mid)*(pnt[i].y+mid))); axis[i].st=pnt[i].x-tmp; axis[i].ed=pnt[i].x+tmp; } ll ans=0; sort(axis,axis+n,cmp); for(ll i=0;i<n;i++){ ans++; if(ans>s)return false; ll t=i+1; while(axis[t].st<=axis[i].ed){ t++; if(t>=n)break; } i=t-1; } if(ans<=s)return true; return false; } int main(){ int T; scanf("%d",&T); for(int tt=1;tt<=T;tt++){ scanf("%lld%lld%lld%lld",&k,&n,&s,&d); for(ll i=0;i<n;i++){ scanf("%lld%lld",&pnt[i].x,&pnt[i].y); pnt[i].y-=k; } ll l=0,r=inf; ll mid,ans; bool has=false; while(l<=r){ mid=(l+r)>>1; if(calc(mid))has=true,l=mid+1,ans=mid; else r=mid-1; } printf("Case %d: ",tt); if(has)printf("%lld\n",ans); else puts("impossible"); } return 0; }