結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー startcpp
提出日時 2014-12-07 20:48:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,182 bytes
コンパイル時間 644 ms
コンパイル使用メモリ 81,648 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-11 17:05:41
合計ジャッジ時間 1,416 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

//太郎君が使う中継所と、二郎君が使う中継所の組み合わせさえ分かればよい。(N=0,1のときは別個処理)
//使う中継所をA,Bとすると、もしもAB間で通信ができるのなら、AB間の距離+2が、通信可能距離となる。
//よって、中継所Aから中継所Bまで通信ができるかというクエリに答えられれば、通信できる組み合わせの内
//直線距離が最大のものを探せばよい。
//このクエリにこたえるには、グラフ構築→幅優先探索が鉄板。Union-Findだともっと高速らしい。
//別に最短距離を知る必要はなくって、連結しているかを知るだけなのだから、楽勝。
//直接通信可能な中継所同士を結んで、ある中継所から行ける中継所を幅優先探索で求めよう。
//追記：TLEしたので、Union-Findする。
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;

int n;
int x[1000],y[1000];

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 >> 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 ){
				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( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) , subans );
			}
		}
	}
	
	double ans = sqrt( (double)subans ) + 2;
	printf("%.15f\n",ans);
	return 0;
}
0