poj1328

2019-11-10 20:41:14

字体：大中小

来源：转载

供稿：网友

题目大意：

地图的x轴的上方为海，下方为陆地，海中有n个小岛，坐标为(isl[i].x,isl[i].y)。有一种雷达，能探测到的范围为以d为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都包含在内。注意雷达是建在海岸线上的，也就是x轴上的。

解题思路：

无

代码如下：

#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>int n,d;double pl[1005],PR[1005];void kp(int L,int R){ double m1=pl[L+R>>1],m2=pr[L+R>>1]; int i=L,j=R; double key; while(i<j) { while(pr[i]<m2) i++; while(pr[j]>m2) j--; if(i<=j) { key=pr[i]; pr[i]=pr[j]; pr[j]=key; key=pl[i]; pl[i]=pl[j]; pl[j]=key; ++i;j--; } } if(i<R) kp(i,R); if(j>L) kp(L,j);}int main(){ int x,y; double temp; int i; int flag; int count; int count_n=0; double place; while(scanf("%d%d",&n,&d)==2) { if(n==0&&d==0) break; count=0; flag=0; count_n++; memset(pl,0,sizeof(pl)); memset(pr,0,sizeof(pr)); for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); if(y>d) { flag=1; } temp=d*d-y*y; temp=sqrt(temp); pl[i]=x-temp; pr[i]=x+temp; } if(flag) { printf("Case %d: -1/n",count_n); } else { while(n) { kp(1,n); place=pr[1]; for(i=1;i<=n;) { if(pl[i]<=place&&pr[i]>=place) { pl[i]=pl[n]; pr[i]=pr[n]; n--; } else i++; } count++; } printf("Case %d: %d/n",count_n,count); } } return 0;}

上一篇：懒虫小鑫

下一篇：JVM-OutOfMemory异常重现