#133754 (C++14) No.96 圏外です。

提出ソース

結果

問題	No.96 圏外です。
ユーザー	izuru_matsuura
提出日時	2016-11-29 18:08:00
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	7,253 bytes
コンパイル時間	2,477 ms
コンパイル使用メモリ	195,380 KB
実行使用メモリ	29,952 KB
最終ジャッジ日時	2024-05-05 15:20:27
合計ジャッジ時間	9,540 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 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	7 ms 5,760 KB
testcase_05	AC	12 ms 7,296 KB
testcase_06	AC	18 ms 8,704 KB
testcase_07	AC	30 ms 12,000 KB
testcase_08	AC	43 ms 14,848 KB
testcase_09	AC	65 ms 20,844 KB
testcase_10	TLE	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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]) <= 0) 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]) <= 0) k--;
        ans.resize(k - 1);
    }

    int next(const vector<Point>& P, int i) {
        int N = P.size();
        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 {
            if (cross(P[next(P, i)] - P[i], P[next(P, 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;
}

yukicoder

結果

テストケース

ソースコード