题意:给出n个岛的坐标,要从第一个到跳到第二个岛,跳的时候有个距离限制,求出这个距离的最小值。
思路:刚开始限制距离为两岛的直接距离,用二分每得到一个距离mid,判断1个2是否能连通。就求出最小的限制距离了。
#include<string.h> #include<math.h> #include<stdio.h> const int N=210; int f[N],n; double map[N][N]; struct node { int x,y; }p[N]; double dist(int i,int j) { return sqrt(1.0*(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)); } int find(int a) { if(a!=f[a])f[a]=find(f[a]); return f[a]; } int judge(double D) { int i,j; for(i=1;i<=n;i++) f[i]=i; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) if(map[i][j]<D)//小于限制的距离 { f[find(i)]=find(find(j)); } } if(find(1)==find(2))return 1; return 0; } int main() { int i,j,op=1; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); for(j=1;j<i;j++) { map[i][j]=map[j][i]=dist(i,j); } } double left,right,mid; left=0;right=map[1][2]; while(right-left>1e-7) { mid=(left+right)/2; if(judge(mid)) { right=mid; } else left=mid; } printf("Scenario #%d\n",op++); printf("Frog Distance = %.3f\n\n",right); } return 0; }