結果

問題 No.94 圏外です。(EASY)
ユーザー startcppstartcpp
提出日時 2014-12-07 20:40:31
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,154 bytes
コンパイル時間 1,007 ms
コンパイル使用メモリ 80,400 KB
実行使用メモリ 35,744 KB
最終ジャッジ日時 2023-09-02 10:22:40
合計ジャッジ時間 12,097 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 5 ms
4,380 KB
testcase_09 AC 149 ms
4,376 KB
testcase_10 AC 210 ms
4,376 KB
testcase_11 AC 13 ms
4,380 KB
testcase_12 AC 61 ms
4,380 KB
testcase_13 AC 32 ms
4,376 KB
testcase_14 AC 2,712 ms
35,744 KB
testcase_15 AC 368 ms
4,380 KB
testcase_16 AC 3,313 ms
13,416 KB
testcase_17 AC 434 ms
4,440 KB
testcase_18 AC 1,826 ms
7,364 KB
testcase_19 AC 15 ms
4,380 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//太郎君が使う中継所と、二郎君が使う中継所の組み合わせさえ分かればよい。(N=0,1のときは別個処理)
//使う中継所をA,Bとすると、もしもAB間で通信ができるのなら、AB間の距離+2が、通信可能距離となる。
//よって、中継所Aから中継所Bまで通信ができるかというクエリに答えられれば、通信できる組み合わせの内
//直線距離が最大のものを探せばよい。
//このクエリにこたえるには、グラフ構築→幅優先探索が鉄板。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];
vector<int> to[1000];

int BFS( int st ){
	queue<int> 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;
}
0