結果
問題 | No.94 圏外です。(EASY) |
ユーザー |
![]() |
提出日時 | 2019-08-17 11:51:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,315 bytes |
コンパイル時間 | 951 ms |
コンパイル使用メモリ | 84,512 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 19:07:37 |
合計ジャッジ時間 | 1,909 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>#include <cmath>using namespace std;template<class T> T dist2(T x, T y) { return x * x + y * y; }struct UnionFind {vector<int> data;int sz;UnionFind(int sz) : data(sz, -1), sz(sz) { }bool unionSet(int x, int y) {if ((x = root(x)) == (y = root(y))) return false;if (data[x] > data[y]) swap(x, y);data[x] += data[y]; data[y] = x; sz--;return true;}bool findSet(int x, int y) { return root(x) == root(y); }int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }int size(int x) { return -data[root(x)]; }int size() { return sz; }};#include <iomanip>int main() {cout << fixed << setprecision(12);int n; cin >> n;vector<int> x(n), y(n);for (int i = 0; i < n; i++) cin >> x[i] >> y[i];UnionFind uf(n);for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {if (dist2(x[i] - x[j], y[i] - y[j]) <= 100) uf.unionSet(i, j);}double ans = (n == 0 ? 1.0 : 2.0);for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {if (uf.findSet(i, j)) {double d = sqrt(dist2(x[i] - x[j], y[i] - y[j])) + 2;ans = max(ans, d);}}cout << ans << endl;return 0;}