結果
問題 | No.3031 曲面の向き付け |
ユーザー |
![]() |
提出日時 | 2025-02-01 16:54:45 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 335 ms / 2,000 ms |
コード長 | 3,579 bytes |
コンパイル時間 | 963 ms |
コンパイル使用メモリ | 94,768 KB |
実行使用メモリ | 61,740 KB |
最終ジャッジ日時 | 2025-02-01 22:01:52 |
合計ジャッジ時間 | 7,439 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
import std.algorithm, std.array, std.conv, std.stdio, std.typecons; class Triangle { uint A, B, C; Triangle nAB, nBC, nAC; // the triangles that share the edges int orientation; this (uint a, uint b, uint c) { A = a, B = b, C = c; assert(A < B && B < C); } // false if already set void set_neighborhood(Triangle n, uint P, uint Q) { if (tuple(P, Q) == tuple(A, B)) { nAB = n; } else if (tuple(P, Q) == tuple(B, C)) { nBC = n; } else if (tuple(P, Q) == tuple(A, C)) { nAC = n; } else assert(0); } // X is A, B or C // 1: A->B->C, -1: A->C->B uint perm(uint X, int o = 0) { if (o == 0) o = this.orientation; if (o == 1) { if (X == A) return B; else if (X == B) return C; else if (X == C) return A; else assert(0); } else if (o == -1) { if (X == B) return A; else if (X == C) return B; else if (X == A) return C; else assert(0); } else assert(0); } } class Triangulation { Triangle[] triangles; bool unorientable = false; this(uint[][] tri_array) { // remove multiple appearance bool[Tuple!(uint, uint, uint)] triangle_set; foreach (tri3; tri_array) { triangle_set[tuple(tri3[0], tri3[1], tri3[2])] = true; } this.triangles = triangle_set.keys.map!(t => new Triangle(t[0], t[1], t[2])).array; // set neighborhoods Triangle[Tuple!(uint, uint)] edges; uint[Tuple!(uint, uint)] edge_appear_times; foreach (triangle; triangles) { foreach (edge; [tuple(triangle.A, triangle.B), tuple(triangle.B, triangle.C), tuple(triangle.A, triangle.C)]) { if (auto neiborhood = edge in edges) { // shared by three triangles if (edge_appear_times[edge] >= 2) { unorientable = true; return; } // set neighborhoods edge_appear_times[edge]++; triangle.set_neighborhood(*neiborhood, edge[0], edge[1]); neiborhood.set_neighborhood(triangle, edge[0], edge[1]); } else { // set neighborhoods edges[edge] = triangle; edge_appear_times[edge] = 1; } } } } // DFS void give_orientation(Triangle triangle, uint P, uint Q) { // already set if (!triangle || triangle.orientation != 0) return; triangle.orientation = triangle.perm(P, 1) == Q ? 1 : -1; // recursively if (triangle.perm(triangle.A) == triangle.B) give_orientation(triangle.nAB, triangle.B, triangle.A); else give_orientation(triangle.nAB, triangle.A, triangle.B); if (triangle.perm(triangle.B) == triangle.C) give_orientation(triangle.nBC, triangle.C, triangle.B); else give_orientation(triangle.nBC, triangle.B, triangle.C); if (triangle.perm(triangle.A) == triangle.C) give_orientation(triangle.nAC, triangle.C, triangle.A); else give_orientation(triangle.nAC, triangle.A, triangle.C); } bool is_orientable() { if (unorientable) return false; foreach (triangle; triangles) { give_orientation(triangle, triangle.A, triangle.B); } // check foreach (triangle; triangles) { with (triangle) // A -> B -> C -> A if (orientation == 1) { if ((nAB && nAB.perm(B) != A) || (nBC && nBC.perm(C) != B) || (nAC && nAC.perm(A) != C)) return false; } // A -> C -> B -> A else if (orientation == -1) { if ((nAB && nAB.perm(A) != B) || (nBC && nBC.perm(B) != C) || (nAC && nAC.perm(C) != A)) return false; } else assert (0); } return true; } } void main() { auto M = readln[0 .. $-1].to!uint; uint[][] tris; foreach (m; 0 .. M) tris ~= readln.split.to!(uint[]); auto trig = new Triangulation(tris); writeln(trig.is_orientable ? "YES" : "NO"); }