結果

問題 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