//太郎君が使う中継所と、二郎君が使う中継所の組み合わせさえ分かればよい。(N=0,1のときは別個処理) //使う中継所をA,Bとすると、もしもAB間で通信ができるのなら、AB間の距離+2が、通信可能距離となる。 //よって、中継所Aから中継所Bまで通信ができるかというクエリに答えられれば、通信できる組み合わせの内 //直線距離が最大のものを探せばよい。 //このクエリにこたえるには、グラフ構築→幅優先探索が鉄板。Union-Findだともっと高速らしい。 //別に最短距離を知る必要はなくって、連結しているかを知るだけなのだから、楽勝。 //直接通信可能な中継所同士を結んで、ある中継所から行ける中継所を幅優先探索で求めよう。 //追記:TLEしたので、Union-Findする。 //追記:中継所間の距離が10以下であるのと、中継所の座標が整数であることを踏まえると、中継所Aと直接通信できる中継所って高々400個だよね(もっと少ないけど)。 //点の座標をソートして枝刈すればとけそう。→間接的に通信できる中継所は多い//のでとけない!! #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n; struct Point{ int px,py; }point[120000]; //px→pyの優先順位でソート int compare( const void *s1, const void *s2 ){ int t1 = ((Point*)s1)->px - ((Point*)s2)->px; int t2 = ((Point*)s1)->py - ((Point*)s2)->py; if( t1 != 0 ) return t1; return t2; } //point[i].px >= lowxとなる最小のiを返す int lower_x( int lowx ){ int st = 0, ed = n-1, medi; while( st <= ed ){ medi = (st+ed)/2; if( point[medi].px >= lowx ){ if( medi == 0 || point[medi-1].px < lowx ) return medi; ed = medi-1; } else{ st = medi+1; } } return medi; } //( point[i].px > lowx || (point[i].px >= lowx && point[i].py) ) >= lowyとなる最小のiを返す int lower_y( int lowx, int lowy ){ int st = 0, ed = n-1, medi; while( st <= ed ){ medi = (st+ed)/2; if( ( point[medi].px > lowx || point[medi].px >= lowx && point[medi].py >= lowy ) ){ if( medi == 0 || !( point[medi].px > lowx || point[medi].px >= lowx && point[medi].py >= lowy ) ) return medi; ed = medi-1; } else{ st = medi+1; } } return medi; } class UnionFind{ public: int num[1000]; void ini( int n ){for( int i = 0; i < n; i++ )num[i] = i;} int root( int x ){if( num[x] == x )return x; return (num[x] = root(num[x]) );} int is_same_root( int x, int y ){x = root(x); y = root(y); return (x==y); } void marge( int x, int y ){x = root(x); y = root(y); if(x!=y){num[x] = y;} } }uf; int main(){ int i,j; cin >> n; uf.ini(n); if( n <= 1 ){ cout << 1 << endl; return 0; } for( i = 0; i < n; i++ ){ cin >> point[i].px >> point[i].py; } qsort( point, n, sizeof(Point), compare ); for( i = 0; i < n; i++ ){ int begin = lower_x( point[i].px - 10 ); for( j = begin; point[j].px <= point[i].px+10 && j < n; ){ int begin2 = max( j, lower_y( point[j].px , point[j].py - 10 ) ); for( j = begin2; point[j].px == point[begin2].px; j++ ){ if( point[j].py > point[begin2].py + 10 ){ j = lower_x( point[j].px + 1 ); break; } if( (point[i].px - point[j].px) * (point[i].px - point[j].px) + (point[i].py - point[j].py)*(point[i].py - point[j].py) <= 100 ){ uf.marge( i, j ); } } } } int subans = 0; for( i = 0; i < n; i++ ){ for( j = 0; j < n; j++ ){ if( uf.is_same_root(i,j) ){ subans = max( subans, (point[i].px - point[j].px) * (point[i].px - point[j].px) + (point[i].py - point[j].py)*(point[i].py - point[j].py) ); } } } double ans = sqrt( (double)subans ) + 2; printf("%.15f\n",ans); return 0; }