結果

問題 No.96 圏外です。
ユーザー startcppstartcpp
提出日時 2014-12-07 21:48:40
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 4,134 bytes
コンパイル時間 837 ms
コンパイル使用メモリ 84,220 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-11 17:35:42
合計ジャッジ時間 5,276 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 2 ms
6,944 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int lower_x(int)’:
main.cpp:44:31: warning: ‘medi’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |         int st = 0, ed = n-1, medi;
      |                               ^~~~
main.cpp: In function ‘int lower_y(int, int)’:
main.cpp:60:31: warning: ‘medi’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |         int st = 0, ed = n-1, medi;
      |                               ^~~~

ソースコード

diff # 

//太郎君が使う中継所と、二郎君が使う中継所の組み合わせさえ分かればよい。(N=0,1のときは別個処理)
//使う中継所をA,Bとすると、もしもAB間で通信ができるのなら、AB間の距離+2が、通信可能距離となる。
//よって、中継所Aから中継所Bまで通信ができるかというクエリに答えられれば、通信できる組み合わせの内
//直線距離が最大のものを探せばよい。
//このクエリにこたえるには、グラフ構築→幅優先探索が鉄板。Union-Findだともっと高速らしい。
//別に最短距離を知る必要はなくって、連結しているかを知るだけなのだから、楽勝。
//直接通信可能な中継所同士を結んで、ある中継所から行ける中継所を幅優先探索で求めよう。
//追記：TLEしたので、Union-Findする。
//追記：中継所間の距離が10以下であるのと、中継所の座標が整数であることを踏まえると、中継所Aと直接通信できる中継所って高々400個だよね(もっと少ないけど)。
//点の座標をソートして枝刈すればとけそう。→間接的に通信できる中継所は多い//のでとけない！！

#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;

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;
}
0