結果
問題 | 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 |
ソースコード
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_iVector vertex(long i) {return points[i >= 0 ? i % $ : (i % cast(long)$ + $) ];}// 0 : not a polygon// 1 : counterclockwise// -1 : clock wiseprivate int _rotation = 2;int rotation() {if (_rotation != 2) return _rotation;// check if three successive points are on the same lineforeach (i; 0 .. this.size()) {if (tri_sgn(vertex(i), vertex(i+1), vertex(i+2)) == 0)return _rotation = 0;}// check self-intersectionforeach (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 : clockwiseint 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 abbool between(Vector a, Vector p, Vector b) {returntri_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 intersectbool 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; }// counterclockwiseauto 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 abif (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();}