HPUOJ--2017寒假作业-专题0/Q-Radar Installation

Q - Radar Installation

 Figure A Sample Input of Radar Installations

3 21 2-3 12 11 20 20 0Sample Output
Case 1: 2Case 2: 1
#include<cstdio>#include<cmath>#include<algorithm>using namespace std; struct il{double x;double y;double p;double st;double endd; }data[1000+11];bool cmp1(il A,il B){return A.endd<B.endd;}bool cmp2(il A,il B){return A.y>B.y;}int main(){	int n,i,m,num=0,t=0;	double d,q;	while(scanf("%d%lf",&n,&d),n!=0||d!=0)	{		t++;		num=1;		for(i=0;i<n;i++)		{			scanf("%lf%lf",&data[i].x,&data[i].y);		}		sort(data,data+n,cmp2);		if(data[0].y>d)		    m=0;		else		{			m=1;			for(i=0;i<n;i++)			{				data[i].p=sqrt(d*d-data[i].y*data[i].y);				data[i].st=data[i].x-data[i].p;				data[i].endd=data[i].x+data[i].p;			}		    sort(data,data+n,cmp1);		    q=data[0].endd;		    for(i=1;i<n;i++)		    {				if (data[i].st > q)		//此雷达覆盖范围外 ，就是说只要能被原来的雷达覆盖就不用添加，一旦不能被覆盖就要添加啦，这个时候再来更新q,只管不能覆盖的就好啦。嘿嘿 。 				{					num++;		//加一个新雷达 					q = data[i].endd;		//尽量靠后放 				}		    }		}		if(m==0)		    printf("Case %d: -1/n",t);		else if(m==1)		    printf("Case %d: %d/n",t,num); 	}	return 0;}