#6611 (C++11) No.94 圏外です。(EASY)

• 問題: No.94 圏外です。(EASY)
• ユーザー: たこし
• 提出日時: 2014-12-17 13:09:02
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 5 ms / 5,000 ms
• コード長: 1,837 bytes
• コンパイル時間: 791 ms
• コンパイル使用メモリ: 94,080 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-26 07:26:18
• 合計ジャッジ時間: 1,624 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	4 ms; 5,376 KB
testcase_09	AC	5 ms; 5,376 KB
testcase_10	AC	5 ms; 5,376 KB
testcase_11	AC	5 ms; 5,376 KB
testcase_12	AC	5 ms; 5,376 KB
testcase_13	AC	5 ms; 5,376 KB
testcase_14	AC	5 ms; 5,376 KB
testcase_15	AC	5 ms; 5,376 KB
testcase_16	AC	5 ms; 5,376 KB
testcase_17	AC	5 ms; 5,376 KB
testcase_18	AC	5 ms; 5,376 KB
testcase_19	AC	4 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB

ソースコード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define EPS 1e-9
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
  
#define MAX_N 1000

int N;
int X[MAX_N], Y[MAX_N];

int par[MAX_N];
int Rank[MAX_N];

void init(int n){
  for(int i = 0; i < n; i++){
    par[i] = i;
    Rank[i] = 0;
  }
}

int find(int x){
  if(x == par[x])
    return x;
  else
    return par[x] = find(par[x]);
}

void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y)
    return;

  if(Rank[x] < Rank[y]){
    par[x] = y;
  }
  else{
    par[y] = x;
    if(Rank[x] == Rank[y])
      Rank[x]++;
  }

}

int calc(int a, int b, int c, int d){
  return (a-c)*(a-c) + (b-d)*(b-d);
}

bool same(int x, int y){
  return find(x) == find(y);
}

int main(){

  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> X[i] >> Y[i];
  }

  init(N);
  
  for(int i = 0; i < N; i++){
    for(int j = i+1; j < N; j++){
      if(calc(X[i],Y[i],X[j],Y[j]) <= 100){
	unite(i,j);
      }
    }
  }
  
  int ans = 0;

  for(int i = 0; i < N; i++){
    for(int j = i+1; j < N; j++){
      if(same(i,j))
	ans = max(ans, calc(X[i],Y[i],X[j],Y[j]));
    }
  }
  
  if(ans == 0 && N == 0)
    cout << 1 << endl;
  else if(ans == 0 && N >= 1)
    cout << 2 << endl;
  else
    printf("%.7f\n",sqrt(ans) + 2.0);
  
  return 0;
  
}