結果

問題 No.3032 ホモトピー入門
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-01-26 19:42:10
言語 D
(dmd 2.109.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,179 bytes
コンパイル時間 1,669 ms
コンパイル使用メモリ 131,612 KB
実行使用メモリ 74,256 KB
最終ジャッジ日時 2025-01-31 19:24:23
合計ジャッジ時間 11,330 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.array, std.container, std.conv, std.math, std.range, std.stdio, std.typecons;

/**********************
Point
**********************/

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);
	}
	
	// lexicographic order
	int opCmp(Vector rhs) {
		if (this.x < rhs.x)
			return -1;
		else if (this.x > rhs.x)
			return 1;
		else {
			if (this.y < rhs.y)
				return -1;
			else if (this.y > rhs.y)
				return 1;
			else
				return 0;
		}
	}
	
	string toString() {
		return "("~x.to!string~", "~y.to!string~")";
	}
}

long det(Vector v, Vector w) {
	return v.x * w.y - v.y * w.x;
}

// 0 : on the same line
// 1 : counterclockwise
// -1 : clockwise
long tri_sgn(Vector a, Vector b, Vector c) {
	return 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;
}

/*********************
 *********************/
bool in_A(Vector p) {
	return
		   tri_sgn(Vector(-4003, 2002), Vector(-1, 1), p) > 0
		&& tri_sgn(Vector(-1, 1), Vector(0, 2002), p) > 0
		&& tri_sgn(Vector(0, 2002), Vector(-4003, 2002), p) > 0;
}
bool in_B(Vector p) {
	return
		   tri_sgn(Vector(-4003, 2002), Vector(0, -2002), p) > 0
		&& tri_sgn(Vector(0, -2002), Vector(-1, 1), p) > 0
		&& tri_sgn(Vector(-1, 1), Vector(-4003, 2002), p) > 0;
}
bool in_C(Vector p) {
	return
		   tri_sgn(Vector(-1, 1), Vector(0, -2002), p) > 0
		&& tri_sgn(Vector(0, -2002), Vector(1, 1), p) > 0
		&& tri_sgn(Vector(1, 1), Vector(-1, 1), p) > 0;
}
bool in_D(Vector p) {
	return
		   tri_sgn(Vector(1, 1), Vector(0, -2002), p) > 0
		&& tri_sgn(Vector(0, -2002), Vector(4003, 2002), p) > 0
		&& tri_sgn(Vector(4003, 2002), Vector(1, 1), p) > 0;
}
bool in_E(Vector p) {
	return
		   tri_sgn(Vector(1, 1), Vector(4003, 2002), p) > 0
		&& tri_sgn(Vector(4003, 2002), Vector(0, 2002), p) > 0
		&& tri_sgn(Vector(0, 2002), Vector(1, 1), p) > 0;
}
bool in_F(Vector p) {
	return
		   tri_sgn(Vector(1, 1), Vector(0, 2002), p) > 0
		&& tri_sgn(Vector(0, 2002), Vector(-1, 1), p) > 0
		&& tri_sgn(Vector(-1, 1), Vector(1, 1), p) > 0;
}

enum Triangle:ubyte {
	A = 1, B = 2, C = 3, D = 4, E = 5, F = 6
}
Triangle triangle(Vector p) {
	if (p.in_A) return Triangle.A;
	if (p.in_B) return Triangle.B;
	if (p.in_C) return Triangle.C;
	if (p.in_D) return Triangle.D;
	if (p.in_E) return Triangle.E;
	if (p.in_F) return Triangle.F;
	assert(0);
}

bool solve(string loop) {
	Triangle[] triangles = [Triangle.C];
	auto p = Vector(0, 0);
	foreach (c; loop) {
		switch (c) {
		case 'U': p.y += 2; break;
		case 'D': p.y -= 2; break;
		case 'L': p.x -= 2; break;
		case 'R': p.x += 2; break;
		default: assert(0);
		}
		auto next = triangle(p);
		with (Triangle)
		if      (triangles[$-1] == B && next == D)
			triangles ~= [C, D];
		else if (triangles[$-1] == D && next == B)
			triangles ~= [C, B];
		else if (triangles[$-1] == A && next == E)
			triangles ~= [F, E];
		else if (triangles[$-1] == E && next == A)
			triangles ~= [F, A];
		else
			triangles ~= next;
	}
	assert(p == Vector(0, 0), p.to!string);
	
	Triangle[] stack = [Triangle.C];
	foreach (t; triangles[1 .. $]) {
		if (stack[$-1] == t)
			continue;
		else if (stack.length > 1 && stack[$-2] == t)
			stack.length--;
		else
			stack ~= t;
	}
	assert(stack.length > 0 && stack[0] == Triangle.C);
	return stack.length == 1;
}

void main() {
	auto NM = readln.split.to!(uint[]);
	auto Cs = iota(NM[0]).map!(i => readln[0 .. $-1]).array;
	Cs.filter!(C => solve(C)).array.length.writeln;
}
0