国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

HPUOJ--2017寒假作業-專題0/Q-Radar Installation

2019-11-10 18:33:36
字體:
來源:轉載
供稿:網友

Q - Radar Installation

 Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a PRogram to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates. 
 Figure A Sample Input of Radar Installations
InputThe input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. The input is terminated by a line containing pair of zeros OutputFor each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.Sample Input
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;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 徐汇区| 荃湾区| 进贤县| 海阳市| 垣曲县| 沛县| 贡觉县| 宽甸| 日喀则市| 丰都县| 张北县| 綦江县| 蓬莱市| 普格县| 科技| 德惠市| 吉林市| 闽清县| 彩票| 凌云县| 赤壁市| 弋阳县| 隆化县| 平顶山市| 赤壁市| 青川县| 布拖县| 五大连池市| 沂源县| 通州区| 新宁县| 凤翔县| 抚顺市| 灵台县| 游戏| 囊谦县| 汉源县| 福建省| 东源县| 海城市| 花垣县|