結果
問題 | No.94 圏外です。(EASY) |
ユーザー |
![]() |
提出日時 | 2020-05-13 17:22:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 2,340 ms |
コンパイル使用メモリ | 170,896 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 15:36:14 |
合計ジャッジ時間 | 2,692 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct UnionFind { vector<int> data; UnionFind(int n) { data.assign(n, -1); } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return (false); if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return (true); } int root(int k) { if (data[k] < 0) return (k); return (data[k] = root(data[k])); } bool same(int x, int y) { return root(x) == root(y); } int size(int k) { return (-data[root(k)]); } }; int main() { int N, X[1010], Y[1010]; cin >> N; for (int i = 0; i < N; i++) { cin >> X[i] >> Y[i]; } auto check = [&](int a, int b) { return abs(X[a] - X[b]) * abs(X[a] - X[b]) + abs(Y[a] - Y[b]) * abs(Y[a] - Y[b]) <= 100; }; UnionFind uf(N); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (check(i, j)) uf.unite(i, j); } } double ans = 1; auto dist = [&](int a, int b) { return sqrt(abs(X[a] - X[b]) * abs(X[a] - X[b]) + abs(Y[a] - Y[b]) * abs(Y[a] - Y[b])) + 2; }; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (uf.same(i, j)) { ans = max(ans, dist(i, j)); } } } cout << fixed << setprecision(7) << ans << endl; }