#135259 (C++14) No.94 圏外です。(EASY)

• 問題: No.94 圏外です。(EASY)
• ユーザー: 0w1
• 提出日時: 2016-12-05 12:10:05
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 2,116 bytes
• コンパイル時間: 1,857 ms
• コンパイル使用メモリ: 180,272 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-26 08:06:01
• 合計ジャッジ時間: 2,690 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 22

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< int, int > pii;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector< pii > vp;
typedef vector< vp > vvp;
typedef vector< string > vs;
typedef vector< double > vd;
typedef vector< vd > vvd;
template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
  if( x > v ){
    x = v;
    return 1;
  }
  return 0;
}
template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
  if( x < v ){
    x = v;
    return 1;
  }
  return 0;
}
const int INF = 0x3f3f3f3f;
int N;
vi X, Y;
void init(){
  cin >> N;
  X = Y = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> X[ i ] >> Y[ i ];
}
struct dsu{
  vi fa;
  dsu( int sz ){
    fa = vi( sz );
    for( int i = 0; i < sz; ++i )
      fa[ i ] = i;
  }
  int find( int x ){
    return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
  }
  int merge( int a, int b ){
    int x = find( a );
    int y = find( b );
    if( x == y )
      return 0;
    fa[ x ] = y;
    return 1;
  }
};
map< int, vi > group;
int eu_dis2( int a, int b, int x, int y ){
  int dx = a - x;
  int dy = b - y;
  return dx * dx + dy * dy;
}
double eu_dis( int a, int b, int x, int y ){
  double dx = a - x;
  double dy = b - y;
  return sqrt( dx * dx + dy * dy ); 
}
void preprocess(){
  dsu *uf = new dsu( N );
  for( int i = 0; i < N; ++i )
    for( int j = i + 1; j < N; ++j )
      if( eu_dis2( X[ i ], Y[ i ], X[ j ], Y[ j ] ) <= 100 )
        uf->merge( i, j );
  for( int i = 0; i < N; ++i )
    group[ uf->find( i ) ].emplace_back( i );
}
void solve(){
  double ans = N == 0 ? 1.0 : 2.0;
  for( auto it = group.begin(); it != group.end(); ++it ){
    for( int i = 0; i < it->second.size(); ++i )
      for( int j = i + 1; j < it->second.size(); ++j )
        upmax( ans, 2.0 + eu_dis( X[ ( it->second )[ i ] ], Y[ ( it->second )[ i ] ], X[ ( it->second )[ j ] ], Y[ ( it->second )[ j ] ] ) );
  }
  cout << fixed << setprecision( 8 ) << ans << endl;
}
signed main(){
  ios::sync_with_stdio( 0 );
  init();
  preprocess();
  solve();
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX