結果

問題 No.3008 ワンオペ警備員
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-08 01:50:20
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 3,077 bytes
コンパイル時間 2,297 ms
コンパイル使用メモリ 93,576 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-08 01:50:24
合計ジャッジ時間 4,002 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.conv, std.math, std.range, std.stdio, std.typecons;
struct Vector {
    long x, y;
    this (long x, long y) {
        this.x = x;
        this.y = y;
    }
    
    Vector opBinary(string op)(Vector rhs) {
        static if (op == "+" || op == "-")
            mixin("return Vector(this.x"~op~"rhs.x, this.y"~op~"rhs.y);");
        else static assert(0);
    }
}
long det(Vector v, Vector w) {
    return v.x * w.y - v.y * w.x;
}
struct Polygon {
    Vector[] points;
    
    this (Vector[] points ...) {
        assert (points.length >= 3);
        this.points = points;
    }
    
    long size() {
        return points.length;
    }
    
    // i-th vertex P_i
    Vector vertex(long i) {
        return points[i >= 0 ? i % $ : (i % cast(long)$ + $) ];
    }
    
    // 0  : not a polygon
    // 1  : counterclockwise
    // -1 : clock wise
    private int _rotation = 2;
    int rotation() {
        if (_rotation != 2) return _rotation;
        
        // check if three successive points are on the same line
        foreach (i; 0 .. this.size()) {
            if (tri_sgn(vertex(i), vertex(i+1), vertex(i+2)) == 0)
                return _rotation = 0;
        }
        
        // check self-intersection
        foreach (j; 2 .. this.size()-1) {
            if (intersect(vertex(0), vertex(  1), vertex(j), vertex(j+1)))
                return _rotation = 0;
        }
        foreach (i; 1 .. this.size()-2) foreach (j; i+2 .. this.size()) {
            if (intersect(vertex(i), vertex(i+1), vertex(j), vertex(j+1))) 
                return _rotation = 0;
        }
        
        auto i = points.minIndex!((p, q) => p.x < q.x || (p.x == q.x && p.y < q.y));
        return _rotation = tri_sgn(vertex(i-1), vertex(i), vertex(i+1));
    }
}
// 0 : on the same line
// 1 : counterclockwise
// -1 : clockwise
int tri_sgn(Vector a, Vector b, Vector c) {
    return cast(int) det(b-a, c-a).sgn;
}
// if the point p is between (allow to be the same point) the line segment ab
bool between(Vector a, Vector p, Vector b) {
    return
        tri_sgn(a, p, b) == 0
     && sgn(p.x - a.x) * sgn(p.x - b.x) <= 0
     && sgn(p.y - a.y) * sgn(p.y - b.y) <= 0;
}
// determine whether line segments ab and cd intersect
bool intersect(Vector a, Vector b, Vector c, Vector d) {
    if (between(a, c, b) || between(a, d, b) || between(c, a, d) || between(c, b, d)) return true;
    auto sign1 = tri_sgn(a, b, c) * tri_sgn(a, b, d);
    auto sign2 = tri_sgn(c, d, a) * tri_sgn(c, d, b);
    if (sign1 < 0 && sign2 < 0) return true;
    return false;
}
int solve(Polygon poly) {
    if (poly.rotation == 0) return 0;
    
    bool[long] visible;
    foreach (i; 0 .. poly.size) { visible[i] = true; }
    
    // counterclockwise
    auto r = poly.rotation > 0 ? iota(0L, poly.size, 1) : iota(poly.size, 0L, -1);
    foreach (i; r) {
        auto a = poly.vertex(i), b = poly.vertex(i+poly.rotation);
        foreach (j; 0 .. poly.size) {
            // j-th vertex is on the right hand side of the line segment ab
            if (visible[j] && tri_sgn(a, b, poly.vertex(j)) < 0) {
                visible[j] = false;
            }
        }
    }
    
    if (visible.values.reduce!"a || b") return 1;
    else return -1;
}
void main() {
    auto N = readln[0 .. $-1].to!ulong;
    Vector[] points;
    foreach (_; 0 .. N) {
        auto xy = readln.split.to!(long[]);
        points ~= Vector(xy[0], xy[1]);
    }
    auto poly = Polygon(points);
    solve(poly).writeln();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0