poj 2253 (二分+判断图连通）
题意：给出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;}