結果

問題 No.96 圏外です。
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-11-29 18:23:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 678 ms / 5,000 ms
コード長 7,337 bytes
コンパイル時間 2,460 ms
コンパイル使用メモリ 195,064 KB
実行使用メモリ 104,240 KB
最終ジャッジ日時 2024-06-06 16:26:08
合計ジャッジ時間 10,521 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 8 ms
5,632 KB
testcase_05 AC 13 ms
7,168 KB
testcase_06 AC 19 ms
8,832 KB
testcase_07 AC 32 ms
12,000 KB
testcase_08 AC 48 ms
14,848 KB
testcase_09 AC 70 ms
20,972 KB
testcase_10 AC 101 ms
24,760 KB
testcase_11 AC 143 ms
34,452 KB
testcase_12 AC 175 ms
42,284 KB
testcase_13 AC 259 ms
47,732 KB
testcase_14 AC 340 ms
64,372 KB
testcase_15 AC 455 ms
75,476 KB
testcase_16 AC 535 ms
88,656 KB
testcase_17 AC 585 ms
102,428 KB
testcase_18 AC 670 ms
102,192 KB
testcase_19 AC 678 ms
102,196 KB
testcase_20 AC 398 ms
98,496 KB
testcase_21 AC 439 ms
91,524 KB
testcase_22 AC 317 ms
104,240 KB
testcase_23 AC 479 ms
101,900 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 390 ms
79,348 KB
testcase_26 AC 544 ms
95,916 KB
testcase_27 AC 442 ms
85,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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.html
    real 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;
}
0