結果

問題 No.3008 ワンオペ警備員
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-07 01:44:10
言語 D
(dmd 2.109.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,047 bytes
コンパイル時間 2,305 ms
コンパイル使用メモリ 92,788 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-07 23:15:52
合計ジャッジ時間 4,548 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 35 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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;
	}
	
	ulong size() {
		return points.length;
	}
	
	// i-th vertex P_i
	Vector vertex(ulong i) {
		return points[i % $];
	}
	
	// 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[ulong] visible;
	foreach (i; 0 .. poly.size) { visible[i] = true; }
	
	// counterclockwise
	auto r = poly.rotation > 0 ? iota(0uL, poly.size, 1) : iota(poly.size, 0uL, -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();
}
0