poj1328

2019-11-10 22:02:46

字體：大中小

來源：轉載

供稿：網友

題目大意：

地圖的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;}

上一篇：POJ 2106 Boolean Expressions(遞歸算法)

下一篇：eclipse安裝Activiti Designer插件