結果
問題 | No.96 圏外です。 |
ユーザー | maine_honzuki |
提出日時 | 2020-05-13 22:52:17 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 207 ms / 5,000 ms |
コード長 | 3,375 bytes |
コンパイル時間 | 2,124 ms |
コンパイル使用メモリ | 187,764 KB |
実行使用メモリ | 114,836 KB |
最終ジャッジ日時 | 2023-10-12 17:08:19 |
合計ジャッジ時間 | 7,930 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
98,356 KB |
testcase_01 | AC | 37 ms
98,220 KB |
testcase_02 | AC | 36 ms
98,216 KB |
testcase_03 | AC | 36 ms
98,088 KB |
testcase_04 | AC | 39 ms
98,600 KB |
testcase_05 | AC | 41 ms
98,872 KB |
testcase_06 | AC | 44 ms
99,264 KB |
testcase_07 | AC | 49 ms
99,540 KB |
testcase_08 | AC | 55 ms
100,396 KB |
testcase_09 | AC | 62 ms
101,104 KB |
testcase_10 | AC | 68 ms
101,176 KB |
testcase_11 | AC | 80 ms
102,924 KB |
testcase_12 | AC | 93 ms
104,420 KB |
testcase_13 | AC | 102 ms
102,960 KB |
testcase_14 | AC | 125 ms
106,612 KB |
testcase_15 | AC | 137 ms
104,224 KB |
testcase_16 | AC | 175 ms
109,696 KB |
testcase_17 | AC | 202 ms
114,836 KB |
testcase_18 | AC | 204 ms
111,924 KB |
testcase_19 | AC | 207 ms
111,348 KB |
testcase_20 | AC | 153 ms
103,280 KB |
testcase_21 | AC | 155 ms
105,808 KB |
testcase_22 | AC | 149 ms
103,696 KB |
testcase_23 | AC | 157 ms
103,844 KB |
testcase_24 | AC | 35 ms
98,212 KB |
testcase_25 | AC | 147 ms
109,984 KB |
testcase_26 | AC | 188 ms
113,464 KB |
testcase_27 | AC | 163 ms
111,756 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> convex_hull(vector<pair<int, int>> V) { auto cross = [](pair<int, int> a, pair<int, int> b, pair<int, int> c) { b.first -= a.first; c.first -= a.first; b.second -= a.second; c.second -= a.second; return (long long)b.first * c.second - (long long)b.second * c.first; }; int n = (int)V.size(); sort(V.begin(), V.end(), [](pair<int, int> a, pair<int, int> b) { return a.first != b.first ? a.first < b.first : a.second < b.second; }); if (n == 1) return V; int k = 0; vector<pair<int, int>> ret(n * 2); for (int i = 0; i < n; i++) { while (k > 1 && cross(ret[k - 1], V[i], ret[k - 2]) >= 0) k--; ret[k++] = V[i]; } for (int i = n - 2, t = k; i >= 0; i--) { while (k > t && cross(ret[k - 1], V[i], ret[k - 2]) >= 0) k--; ret[k++] = V[i]; } ret.resize(k - 1); return ret; } 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)]); } }; vector<int> B[2010][2010]; int main() { int N; vector<pair<int, int>> V; cin >> N; for (int i = 0; i < N; i++) { int x, y; cin >> x >> y; V.push_back({x + 10000, y + 10000}); } if (N == 0) { cout << 1 << endl; return 0; } UnionFind uf(N); auto check = [&](int a, int b) { int xa = V[a].first, ya = V[a].second, xb = V[b].first, yb = V[b].second; return abs(xa - xb) * abs(xa - xb) + abs(ya - yb) * abs(ya - yb) <= 100; }; for (int i = 0; i < N; i++) { int& x = V[i].first; int& y = V[i].second; int X = x / 10 + 1; int Y = y / 10 + 1; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { for (auto& n : B[X + dx][Y + dy]) { if (check(i, n)) uf.unite(i, n); } } } B[X][Y].push_back(i); } map<int, vector<int>> V2; for (int i = 0; i < N; i++) { if (!V2.count(uf.root(i))) { V2[uf.root(i)].reserve(uf.size(i)); } V2[uf.root(i)].push_back(i); } auto dist = [](const pair<int, int>& a, const pair<int, int>& b) { return sqrt(abs(a.first - b.first) * abs(a.first - b.first) + abs(a.second - b.second) * abs(a.second - b.second)); }; double ans = 0; for (auto& p : V2) { vector<pair<int, int>> V3; V3.reserve(p.second.size()); for (auto& a : p.second) V3.push_back({V[a].first, V[a].second}); V3 = convex_hull(V3); for (auto& a : V3) for (auto& b : V3) ans = max(ans, dist(a, b) + 2); } cout << fixed << setprecision(9) << ans << endl; }