結果

問題 No.168 ものさし
コンテスト
ユーザー IL_msta
提出日時 2015-07-11 20:08:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 715 ms / 2,000 ms
コード長 2,695 bytes
コンパイル時間 731 ms
コンパイル使用メモリ 87,060 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-12-24 07:10:02
合計ジャッジ時間 6,049 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

#include <algorithm>
#include <cmath>

#include <string>
#include <array>
#include <list>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>

/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;

#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////
unsigned long long Len[1000][1000];

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(10);//

	/*unsigned long long asd;
	asd = 1000000000;
	P(asd*asd*2);
	return 0;
	*/
	int N;
	cin>>N;//[2,1000]
	unsigned long long X[1000],Y[1000];
	rep(i,N){
		cin>>X[i]>>Y[i];
	}
	unsigned long long Lmin=0,tLmin;
	unsigned long long Amax=0;
	for(int i=0;i<N;++i){
		Lmin = 0xFFFFFFFFFFFFFFFF;
		for(int k=0;k<N;++k){
			if(i==k)continue;
			if(X[k] > X[i] ){
				Len[i][k] = (X[k]-X[i])*(X[k]-X[i]);
			}else{
				Len[i][k] = (X[i]-X[k])*(X[i]-X[k]);
			}
			if(Y[k] > Y[i] ){
				Len[i][k] += (Y[k]-Y[i])*(Y[k]-Y[i]);
			}else{
				Len[i][k] += (Y[i]-Y[k])*(Y[i]-Y[k]);
			}
		}
	}
	///////////
	bool use[1001];
	int team[1001];
	int useCount = 0;
	rep(i,N){
		use[i]=false;
		team[i] = i;
	}
	use[0] = true;
	++useCount;
	
	Lmin=0;
	//tLmin;
	Amax = 0;
	int minNo = -1;
	int minI,minK;
	//while(useCount < N)
	while(team[N-1] != 0)
	{
		minNo = -1;
		Lmin = 0;
		minI = -1;
		minK = -1;
		for(int i=0;i<N;++i){
			for(int k=i+1;k<N;++k){
				if(i==k)continue;
				if(team[i] == team[k])continue;
				tLmin = Len[i][k];
				if(Lmin == 0 || Lmin > tLmin){
					Lmin = tLmin;
					minNo = k;
					minI = i;
					minK = k;
				}
			}
		}
		////
		if(team[minI] < team[minK]){
			minNo = team[minK];
			for(int no=0;no<N;++no){
				if(team[no] == minNo){
					team[no] = team[minI];
				}
			}
		}else{
			minNo = team[minI];
			for(int no=0;no<N;++no){
				if(team[no] == minNo ){
					team[no] = team[minK];
				}
			}
		}
		if(Lmin != 0){
			Amax = max(Amax,Lmin);
		}
		++useCount;
		//cout << minI << " " << minK << " " << Lmin << endl;
	}
	
	///////////
	//unsigned long long ans = (LL)sqrt((LD)Amax);
	unsigned long long ans,Left,Right,Mid;

	///////////////
	Left = 0;
	Right = 1414213563;
	{
		do
		{
			Mid = (Right+Left)/2;
			if( Mid*Mid < Amax){
				Left = Mid;
			}else if( Amax < Mid*Mid ){
				Right = Mid; 
			}else{
				break;
			}
		}while( Mid*Mid > Amax || Amax > (Mid+1)*(Mid+1) );
		ans = Mid;
	}
	///////////////
	ans = (ans + 9)/10*10;
	while(Amax > ans*ans){
		ans += 10;
	}
	//ans *= 10;
	P( ans );
    return 0;
}
0