結果

問題 No.94 圏外です。(EASY)
ユーザー startcppstartcpp
提出日時 2014-12-07 20:48:57
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 AC 8 ms
6,940 KB
testcase_10 AC 10 ms
6,940 KB
testcase_11 AC 9 ms
6,944 KB
testcase_12 AC 8 ms
6,944 KB
testcase_13 AC 8 ms
6,944 KB
testcase_14 AC 9 ms
6,944 KB
testcase_15 AC 8 ms
6,940 KB
testcase_16 AC 8 ms
6,940 KB
testcase_17 AC 8 ms
6,944 KB
testcase_18 AC 8 ms
6,940 KB
testcase_19 AC 7 ms
6,940 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

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