//太郎君が使う中継所と、二郎君が使う中継所の組み合わせさえ分かればよい。(N=0,1のときは別個処理) //使う中継所をA,Bとすると、もしもAB間で通信ができるのなら、AB間の距離+2が、通信可能距離となる。 //よって、中継所Aから中継所Bまで通信ができるかというクエリに答えられれば、通信できる組み合わせの内 //直線距離が最大のものを探せばよい。 //このクエリにこたえるには、グラフ構築→幅優先探索が鉄板。Union-Findだともっと高速らしい。 //別に最短距離を知る必要はなくって、連結しているかを知るだけなのだから、楽勝。 //直接通信可能な中継所同士を結んで、ある中継所から行ける中継所を幅優先探索で求めよう。 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n; int x[1000],y[1000]; vector to[1000]; int BFS( int st ){ queue que; int use[1000] = {0}; int now; que.push( st ); while( !que.empty() ){ now = que.front(); que.pop(); use[now] = 1; for( int i = 0; i < to[now].size(); i++ ){ if( use[ to[now][i] ] ) continue; que.push( to[now][i] ); } } int ret = 0; for( int i = 0; i < n; i++ ){ if( use[i] ){ ret = max( ret, (x[st] - x[i]) * (x[st] - x[i]) + (y[st] - y[i]) * (y[st] - y[i]) ); } } return ret; } int main(){ int i,j; cin >> n; if( n <= 1 ){ cout << 1 << endl; return 0; } for( i = 0; i < n; i++ ){ cin >> x[i] >> y[i]; } for( i = 0; i < n; i++ ){ for( j = 0; j < n; j++ ){ if( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= 100 ){ to[i].push_back(j); } } } int subans = 0; for( i = 0; i < n; i++ ){ subans = max( BFS(i) , subans ); } double ans = sqrt( (double)subans ) + 2; printf("%.15f\n",ans); return 0; }