結果
| 問題 | No.96 圏外です。 |
| ユーザー |
 izuru_matsuura
|
| 提出日時 | 2016-11-29 18:23:43 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 592 ms / 5,000 ms |
| コード長 | 7,337 bytes |
| コンパイル時間 | 2,183 ms |
| コンパイル使用メモリ | 195,216 KB |
| 実行使用メモリ | 104,240 KB |
| 最終ジャッジ日時 | 2024-12-24 08:44:57 |
| 合計ジャッジ時間 | 9,635 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#define whole(xs) xs.begin(),xs.end()using namespace std;namespace {typedef double real;typedef long long ll;const real EPS = 1e-8;template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {if (vs.empty()) return os << "[]";auto i = vs.begin();os << "[" << *i;for (++i; i != vs.end(); ++i) os << " " << *i;return os << "]";}template<class T> istream& operator>>(istream& is, vector<T>& vs) {for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;return is;}struct Point {ll x, y;int index;Point() {}Point(ll x, ll y) : x(x), y(y) {}Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }static bool compX(const Point& a, const Point& b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }static bool compY(const Point& a, const Point& b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }};istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }ostream& operator<<(ostream& os, const Point& p) { return os << "Point(" << p.x << "," << p.y << ")"; }struct Node {Node* parent;shared_ptr<Node> left, right;ll left_x, right_x;vector<Point> ys;};ostream& operator<<(ostream& os, const Node& node) {return os << "( [" << node.left_x << "," << node.right_x << "] -> " << node.ys;}shared_ptr<Node> construct(vector<Point>::iterator lb, vector<Point>::iterator ub) {auto n = make_shared<Node>();n->left_x = lb->x;n->right_x = (ub - 1)->x;if (ub - lb == 1) {n->ys.clear(); n->ys.push_back(*lb);return n;}auto mid = lb + (ub - lb) / 2;auto l = construct(lb, mid),r = construct(mid, ub);l->parent = n.get();r->parent = n.get();n->left = l;n->right = r;size_t li = 0, ri = 0;while (true) {if (li >= l->ys.size() && ri >= r->ys.size()) break;if (li >= l->ys.size()) n->ys.push_back(r->ys[ri++]);else if (ri >= r->ys.size()) n->ys.push_back(l->ys[li++]);else {n->ys.push_back( l->ys[li].y < r->ys[ri].y ? l->ys[li++] : r->ys[ri++] );}}return n;}void query(shared_ptr<Node> root, ll sx, ll sy, ll gx, ll gy, vector<Point>& result) {if (gx < root->left_x || root->right_x < sx) {// do nothing;} else if (sx <= root->left_x && root->right_x <= gx) {auto& ys = root->ys;auto lb = upper_bound(whole(ys), Point(0, sy - 1), Point::compY);auto ub = lower_bound(whole(ys), Point(0, gy + 1), Point::compY);result.insert(result.end(), lb, ub);} else {query(root->left, sx, sy, gx, gy, result);query(root->right, sx, sy, gx, gy, result);}}struct UnionFind {int N;vector<int> P;UnionFind(int N) : N(N) {P.clear(); P.resize(N, -1);}int root(int x) {if (P[x] == -1) return x;return P[x] = root(P[x]);}int query(int x, int y) {return root(x) == root(y);}void merge(int x, int y) {x = root(x); y = root(y);if (x == y) return;P[x] = y;}};real dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }real cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }real norm(const Point& a) { return sqrt(dot(a, a)); }int ccw(Point a, Point b, Point c){b = b - a; c = c - a;if (cross(b, c) > EPS) return +1;if (cross(b, c) < -EPS) return -1;if (dot(b, c) < 0) return +2;if (norm(b) < norm(c)) return -2;return 0;}void convexHull(vector<Point> ps, vector<Point>& ans) {assert(ps.size() >= 3);sort(ps.begin(), ps.end(), Point::compX);int N = ps.size();int k = 0;ans.resize(N * 2);for (int i = 0; i < N; ans[k++] = ps[i++])while (k >= 2 && ccw(ans[k - 2], ans[k - 1], ps[i]) == -1) k--;for (int i = N - 2, t = k + 1; i >= 0; ans[k++] = ps[i--])while (k >= t && ccw(ans[k - 2], ans[k - 1], ps[i]) == -1) k--;ans.resize(k - 1);}int next(int N, int i) {return (i + 1) % N;}// from http://www.prefield.com/algorithm/geometry/convex_diameter.htmlreal farthest(const vector<Point>& P) {const int n = P.size();int is = 0, js = 0;for (int i = 1; i < n; i++) {if (P[i].y < P[is].y) is = i;if (P[i].y > P[js].y) js = i;}real maxd = norm(P[is] - P[js]);int i, maxi, j, maxj;i = maxi = is;j = maxj = js;do {//cerr << "(is, js) = " << is << " " << js << endl;//cerr << "(i, j) = " << i << " " << j << endl;if (cross(P[next(n, i)] - P[i], P[next(n, j)] - P[j]) >= 0) j = (j + 1) % n;else i = (i + 1) % n;if (norm(P[i] - P[j]) > maxd) {maxd = norm(P[i] - P[j]);maxi = i; maxj = j;}} while (i != is || j != js);return maxd; /* farthest pair is (maxi, maxj). */}int N;vector<Point> P;void input() {cin >> N;P.clear(); P.resize(N);for (int i = 0; i < N; i++) {cin >> P[i];P[i].index = i;}}ll dist_sq(const Point& a, const Point& b) {ll dx = a.x - b.x;ll dy = a.y - b.y;return dx * dx + dy * dy;}void solve() {if (N == 0) {cout << fixed << setprecision(12) << 1 << endl;return;}vector<Point> ps = P;sort(ps.begin(), ps.end(), Point::compX);auto root = construct(ps.begin(), ps.end());UnionFind uf(N);for (int i = 0; i < N; i++) {int x = P[i].x, y = P[i].y;vector<Point> ns;query(root, x - 10, y - 10, x + 10, y + 10, ns);for (auto& n : ns) {if (P[i].index == n.index) continue;if (dist_sq(n, P[i]) <= 100) {uf.merge(P[i].index, n.index);}}}real ans = 0;map<int, vector<Point>> gs;for (int i = 0; i < N; i++) {gs[uf.root(i)].push_back(P[i]);}for (auto& g : gs) {auto vs = g.second;if (vs.size() == 1) {// do nothing} else if (vs.size() == 2) {ans = max(ans, norm(vs[0] - vs[1]));} else {vector<Point> hull;convexHull(vs, hull);ans = max(ans, farthest(hull));}}cout << fixed << setprecision(12) << ans + 2 << endl;}}int main() {input(); solve();return 0;}