結果
問題 | No.96 圏外です。 |
ユーザー | 古寺いろは |
提出日時 | 2015-04-10 22:21:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,748 bytes |
コンパイル時間 | 1,389 ms |
コンパイル使用メモリ | 158,804 KB |
実行使用メモリ | 109,840 KB |
最終ジャッジ日時 | 2023-09-17 19:14:57 |
合計ジャッジ時間 | 5,829 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
100,652 KB |
testcase_01 | AC | 40 ms
100,712 KB |
testcase_02 | AC | 39 ms
100,780 KB |
testcase_03 | AC | 39 ms
100,596 KB |
testcase_04 | AC | 42 ms
100,876 KB |
testcase_05 | AC | 43 ms
100,924 KB |
testcase_06 | AC | 45 ms
101,096 KB |
testcase_07 | AC | 47 ms
101,456 KB |
testcase_08 | AC | 52 ms
101,888 KB |
testcase_09 | AC | 57 ms
101,952 KB |
testcase_10 | AC | 63 ms
102,520 KB |
testcase_11 | AC | 71 ms
103,128 KB |
testcase_12 | AC | 78 ms
103,952 KB |
testcase_13 | AC | 96 ms
104,476 KB |
testcase_14 | AC | 106 ms
105,404 KB |
testcase_15 | WA | - |
testcase_16 | AC | 134 ms
107,832 KB |
testcase_17 | AC | 144 ms
109,840 KB |
testcase_18 | AC | 172 ms
109,496 KB |
testcase_19 | AC | 162 ms
109,104 KB |
testcase_20 | AC | 167 ms
107,196 KB |
testcase_21 | AC | 150 ms
109,060 KB |
testcase_22 | AC | 344 ms
107,104 KB |
testcase_23 | AC | 339 ms
107,020 KB |
testcase_24 | AC | 39 ms
100,876 KB |
testcase_25 | AC | 111 ms
107,068 KB |
testcase_26 | AC | 137 ms
108,996 KB |
testcase_27 | AC | 121 ms
107,724 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; typedef complex<double> P; namespace std { bool operator < (const P& a, const P& b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); } } #define EPS 1e-8 struct C { P p; double r; C(const P &p, double r) : p(p), r(r) { } }; bool xy_less(const P& a, const P& b) { if (abs(a.imag() - b.imag()) < EPS) return (a.real() < b.real()); return (a.imag() < b.imag()); } double ccw(P a, P b, P c) { return (conj(b - a)*(c - a)).imag(); } template<class IN> void walk_rightside(IN begin, IN end, vector<P>& v) { IN cur = begin; v.push_back(*cur++); vector<P>::size_type s = v.size(); v.push_back(*cur++); while (cur != end) { if (v.size() == s || ccw(v[v.size() - 2], v.back(), *cur) > EPS) v.push_back(*cur++); else v.pop_back(); } v.pop_back(); } vector<P> convex_hull(vector<P> v) { if (v.size() <= 1) return v; // EXCEPTIONAL sort(v.begin(), v.end(), xy_less); vector<P> cv; walk_rightside(v.begin(), v.end(), cv); walk_rightside(v.rbegin(), v.rend(), cv); return cv; } vector<int> box[2004][2004]; vector<P> p2[130002]; int unidp[130002]; int findunidp(int a){ if (unidp[a] < 0) return a; else return unidp[a] = findunidp(unidp[a]); } bool connect(int a, int b){ a = findunidp(a); b = findunidp(b); if (a == b) return false; unidp[a] += unidp[b]; unidp[b] = a; return true; } int main(){ int N; cin >> N; vector<P> ps; for (int i = 0; i < N; i++) { int X, Y; cin >> X >> Y; ps.push_back(P(X + 10000, Y + 10000)); unidp[i] = -1; } if (N == 0){ cout << 1 << endl; return 0; } for (int i = 0; i < N; i++) { int Xb = (int)(ps[i].real()) / 10 + 1; int Yb = (int)(ps[i].imag()) / 10 + 1; for (int dy = -1; dy <= 1; dy++) { for (int dx = -1; dx <= 1; dx++) { int nXb = Xb + dx; int nYb = Yb + dy; for (int j : box[nXb][nYb]) { if (abs(ps[i] - ps[j]) <= 10){ connect(i, j); } } } } box[Xb][Yb].push_back(i); } for (int i = 0; i < N; i++) { p2[findunidp(i)].push_back(ps[i]); } double ans = 0; for (int i = 0; i < N; i++) { if (p2[i].size() < 2) continue; vector<P> p3 = convex_hull(p2[i]); int M = p3.size(); int p = 0; int q = 0; vector<double> dist(M, 0); for (int j = 0; j < M; j++) { while (true){ q = p + 1; q %= M; double d1 = abs(p3[j] - p3[p]); double d2 = abs(p3[j] - p3[q]); ans = max(ans, d2); dist[j] = max(dist[j], d1); if (d1 >= d2) break; p = q; } /* while (true){ int k = j - 1; if (k < 0){ break; } double d = abs(p3[k] - p3[p]); if (dist[k] < d){ dist[k] = d; j = k; } else break; } */ } } ans += 2; printf("%.14f\n", ans); }