結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー たこし
提出日時 2014-12-17 13:09:02
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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