結果
問題 | No.96 圏外です。 |
ユーザー | koba-e964 |
提出日時 | 2017-01-06 13:18:06 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,023 bytes |
コンパイル時間 | 872 ms |
コンパイル使用メモリ | 72,520 KB |
実行使用メモリ | 121,636 KB |
最終ジャッジ日時 | 2024-05-10 00:50:03 |
合計ジャッジ時間 | 13,566 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
107,072 KB |
testcase_01 | AC | 78 ms
106,944 KB |
testcase_02 | AC | 77 ms
107,112 KB |
testcase_03 | AC | 78 ms
106,668 KB |
testcase_04 | AC | 82 ms
107,188 KB |
testcase_05 | AC | 85 ms
107,392 KB |
testcase_06 | AC | 86 ms
107,580 KB |
testcase_07 | AC | 89 ms
107,776 KB |
testcase_08 | AC | 94 ms
108,280 KB |
testcase_09 | AC | 102 ms
108,800 KB |
testcase_10 | AC | 107 ms
109,184 KB |
testcase_11 | AC | 116 ms
110,196 KB |
testcase_12 | AC | 130 ms
111,084 KB |
testcase_13 | AC | 142 ms
111,284 KB |
testcase_14 | AC | 158 ms
113,152 KB |
testcase_15 | AC | 187 ms
113,024 KB |
testcase_16 | AC | 209 ms
115,584 KB |
testcase_17 | AC | 230 ms
118,284 KB |
testcase_18 | AC | 244 ms
117,504 KB |
testcase_19 | AC | 246 ms
117,412 KB |
testcase_20 | AC | 2,913 ms
113,580 KB |
testcase_21 | TLE | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
ソースコード
#include <algorithm> #include <iostream> #include <cstdio> #include <cmath> #include <vector> /* * Union-Find tree * header requirement: vector */ class UnionFind { private: std::vector<int> disj; std::vector<int> rank; public: UnionFind(int n) : disj(n), rank(n) { for (int i = 0; i < n; ++i) { disj[i] = i; rank[i] = 0; } } int root(int x) { if (disj[x] == x) { return x; } return disj[x] = root(disj[x]); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) { return; } if (rank[x] < rank[y]) { disj[x] = y; } else { disj[y] = x; if (rank[x] == rank[y]) { ++rank[x]; } } } bool is_same_set(int x, int y) { return root(x) == root(y); } }; #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; const double EPS=1e-9; const int N = 120001; int x[N], y[N]; const int W = 2100; const int B = 10; VI board[W][W]; int main(void){ int n; cin >> n; if (n == 0) { cout << 1 << endl; return 0; } const int BIAS = 10000; UnionFind uf(n); REP(i, 0, n) { cin >> x[i] >> y[i]; x[i] += BIAS; y[i] += BIAS; board[x[i] / B][y[i] / B].push_back(i); } REP(i, 0, n) { REP(a, -1, 2) { REP(b, -1, 2) { if (x[i] / B + a < 0 || y[i] / B + b < 0) { continue; } VI &neighbor = board[x[i] / B + a][y[i] / B + b]; REP(k, 0, neighbor.size()) { int j = neighbor[k]; int dist = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); if (dist <= 100) { uf.unite(i, j); } } } } } ll ma = 0; vector<VI> conn(n); REP(i, 0, n) { conn[uf.root(i)].push_back(i); } REP(i, 0, n) { VI &t = conn[i]; REP(j, 0, t.size()) { REP(k, j + 1, t.size()) { int a = t[j]; int b = t[k]; ll dist = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]); ma = max(ma, dist); } } } printf("%.9f\n", 2 + sqrt(ma)); }