結果

問題 No.96 圏外です。
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-11-30 14:33:09
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 3,019 ms / 5,000 ms
コード長 6,743 bytes
コンパイル時間 3,459 ms
コンパイル使用メモリ 177,024 KB
実行使用メモリ 83,416 KB
最終ジャッジ日時 2024-06-12 05:17:56
合計ジャッジ時間 12,988 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 6 ms
6,944 KB
testcase_05 AC 10 ms
6,944 KB
testcase_06 AC 16 ms
6,940 KB
testcase_07 AC 26 ms
6,940 KB
testcase_08 AC 34 ms
7,068 KB
testcase_09 AC 49 ms
9,468 KB
testcase_10 AC 75 ms
13,968 KB
testcase_11 AC 90 ms
17,176 KB
testcase_12 AC 109 ms
21,524 KB
testcase_13 AC 190 ms
29,140 KB
testcase_14 AC 194 ms
33,724 KB
testcase_15 AC 325 ms
37,888 KB
testcase_16 AC 305 ms
43,160 KB
testcase_17 AC 308 ms
54,912 KB
testcase_18 AC 386 ms
53,824 KB
testcase_19 AC 397 ms
50,816 KB
testcase_20 AC 593 ms
56,340 KB
testcase_21 AC 369 ms
40,704 KB
testcase_22 AC 1,161 ms
83,416 KB
testcase_23 AC 3,019 ms
52,512 KB
testcase_24 AC 1 ms
5,376 KB
testcase_25 AC 210 ms
33,152 KB
testcase_26 AC 275 ms
40,192 KB
testcase_27 AC 236 ms
39,128 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(183): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

diff # 

import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stderr.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

const EPS = 1e-7;

struct Point {
    long x, y;
    int index;
    Point opBinary(string op)(in Point p) const if (op == "+" || op == "-") {
        return Point(mixin("x" ~ op ~ "p.x"), mixin("y" ~ op ~ "p.y"));
    }
};
class RangeTree {
    class Node {
        Node parent;
        Node left, right;
        long left_x, right_x;
        Point[] ys;
        override string toString() const {
            return format("([%s,%s] -> %s)", left_x, right_x, ys);
        }
    }
    Node construct(Point[] ps) {
        auto n = new Node;
        n.left_x = ps.front.x;
        n.right_x = ps.back.x;
        if(ps.length <= 1024) {
            n.ys = ps.dup.sort!"a.y < b.y".array;
            return n;
        }
        auto l = construct(ps[0 .. $ / 2]);
        auto r = construct(ps[$ / 2 .. $]);
        l.parent = n;
        r.parent = n;
        n.left = l;
        n.right = r;
        auto li = 0, ri = 0;
        while (true) {
            if (li >= l.ys.length && ri >= r.ys.length) break;
            if (li >= l.ys.length) n.ys ~= r.ys[ri++];
            else if (ri >= r.ys.length) n.ys ~= l.ys[li++];
            else {
                n.ys ~= (l.ys[li].y < r.ys[ri].y ? l.ys[li++] : r.ys[ri++]);
            }
        }
        return n;
    }
    Node root;
    this(Point[] ps) {
        ps.sort!"a.x < b.x";
        this.root = construct(ps);
    }
    /* (sx <= x <= gx && sy <= y <= gy)なる点(x, y)をresultに入れる. 閉区間なの注意 */
    Point[] query(long sx, long sy, long gx, long gy) {
        Point[] result;
        void f(Node cur_root) {
            if (gx < cur_root.left_x || cur_root.right_x < sx) {
                // do nothing
            } else if (sx <= cur_root.left_x && cur_root.right_x <= gx) {
                auto ys = cur_root.ys;
                result ~= ys.assumeSorted!"a.y < b.y".upperBound(Point(0, sy - 1)).lowerBound(Point(0, gy + 1)).array;
            } else {
                if(cur_root.left is null || cur_root.right is null) {
                    foreach (p; cur_root.ys.assumeSorted!"a.y < b.y".upperBound(Point(0, sy - 1)).lowerBound(Point(0, gy + 1))) {
                        if (sx <= p.x && p.x <= gx && sy <= p.y && p.y <= gy) {
                            result ~= p;
                        }
                    }
                } else {
                    f(cur_root.left);
                    f(cur_root.right);
                }
            }
        }
        f(root);
        return result;
    }
}

class UnionFind {
    int[] P;
    this(int N) {
        P = new int[N];
        P[] = -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(in Point a, in Point b) { return a.x * b.x + a.y * b.y; }
real cross(in Point a, in Point b) { return a.x * b.y - a.y * b.x; }
real norm(in 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;      // a,b,cの順に反時計周り
    if (cross(b, c) < -EPS) return -1;     // a,b,cの順に時計周り                       
    if (dot(b, c) < 0) return +2;          // c--a--b 直線                       
    if (norm(b) < norm(c)) return -2;      // a--b--c 直線                       
    return 0;                              // a--c--b 直線
}

Point[] convexHull(in Point[] _ps) {
    auto ps = _ps.dup;
    assert(ps.size() >= 3);
    ps.sort!"a.x == b.x ? a.y < b.y : a.x < b.x";
    int N = ps.size;
    int k = 0;
    auto ans = new Point[2 * N];
    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--;
    /* 返上の点も頂点としたい場合は上4行を
     *     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--;
     * にする. */
    return ans[0 .. k - 1];
}

real diameter(in Point[] P) { // Pは凸多角形であり, かつその頂点は反時計回りでなければならない
    int N = P.size;
    int s = 0, t = 0;
    for (int k = 1; k < N; k++) {
        if (P[k].y < P[s].y) s = k;
        if (P[k].y > P[t].y) t = k;
    }
    real maxd = norm(P[s] - P[t]);
    int i = s, maxi = s;
    int j = t, maxj = t;
    int next(int k) { return (k + 1) % N; }
    do {
        if (cross(P[next(i)] - P[i], P[next(j)] - P[j]) >= 0) j = next(j);
        else i = next(i);
        if (norm(P[i] - P[j]) > maxd) {
            maxd = norm(P[i] - P[j]);
            maxi = i; maxj = j;
        }
    } while (i != s || j != t);
    return maxd; /* farthest pair is (maxi, maxj). */
}

long dist_sq(in Point a, in Point b) {
    auto dx = a.x - b.x;
    auto dy = a.y - b.y;
    return dx * dx + dy * dy;
}

void main() {
    int N = readln.chomp.to!int;
    if (N == 0) {
        writefln("%.12f", 1.0);
        return;
    }
    auto P = new Point[N];
    foreach (int i, ref p; P) {
        readf("%s %s\n", &p.x, &p.y);
        p.index = i;
    }
    auto t = new RangeTree(P.dup);
    auto uf = new UnionFind(N);
    foreach (i; 0 .. N) {
        long x = P[i].x, y = P[i].y;
        auto ns = t.query(x - 10, y - 10, x + 10, y + 10);
        foreach (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;
    Point[][int] gs;
    for (int i = 0; i < N; i++) {
        int k = uf.root(i);
        if (k in gs) {
            gs[k] ~= P[i];
        } else {
            gs[k] = [P[i]];
        }
    }
    foreach (vs; gs) {
        if (vs.size == 1) {
            // do nothing
        } else if (vs.size == 2) {
            ans = max(ans, norm(vs[0] - vs[1]));
        } else {
            auto hull = vs.convexHull;
            ans = max(ans, hull.diameter);
        }
    }
    writefln("%.12f", ans + 2.0);
}
0