No.3031 曲面の向き付け
タグ : / 解いたユーザー数 35
作問者 :

注意
この問題は YES
または NO
と出力する問題です。
問題文
入力から $1 \leq A_m < B_m < C_m \leq 10^8$ となる整数 $A_m, B_m, C_m$ がそれぞれ $M$ 個与えられます。
$\Delta_m = \{ A_m, B_m, C_m\}$ と置き、$\mathcal T = \{ \Delta_1, \dots, \Delta_M \}$ と置きます。
ただし、$\Delta_m$ たちは相異なるように与えられます。
$\Delta = \{ A, B, C \}\ (A < B < C)$ の「向き付け」とは、
- $\sigma(A) = B, \ \sigma(B) = C, \ \sigma(C) = A$ で定義される関数 $\sigma : \Delta \rightarrow \Delta$
- $\sigma(A) = C, \ \sigma(B) = A, \ \sigma(C) = B$ で定義される関数 $\sigma : \Delta \rightarrow \Delta$
各 $\Delta_m \in \mathcal T$ の向き付け $\sigma_m$ を次の条件を満たすようにうまく取れるとき、「$\mathcal T$ は向き付け可能」と言います:
- 任意の $A, B \in \Delta_m \cap \Delta_n \ (n \neq m)$ に対して、$\sigma_m(A) = B \Leftrightarrow \sigma_n(B) = A.$
$\mathcal T$ が向き付け可能であるときは YES
を、そうでないときは NO
を出力してください。
背景
位相幾何学において、曲面の向き付けとは、直観的には「表裏」を決めるものです。例えば、メビウスの帯は表と裏を決めることができません。曲面を小さな三角形に分割した「三角形分割」を考えます。
三角形には表と裏があり、頂点の回転方向に合わせて右ねじを回転させたときに、右ねじの移動する方向の面を表だと思うことにします。となりあう三角形の表の面が一致するように定められるときに、「向き付け可能である」と言います。
本問題は、三角形分割の頂点の情報だけを抜き出したデータから、それが向き付け可能であるか否かを判別させる問題です。
入力
$M$ $A_1 \ B_1 \ C_1$ $\vdots$ $A_M \ B_M \ C_M$
$1 \leq M < 10^5,$
$1 \leq A_m < B_m < C_m \leq 10^8$
出力
最後に改行してください。
サンプル
サンプル1
入力
1 1 2 3
出力
YES
明らかに向き付け可能である。
サンプル2
入力
3 1 2 3 1 2 4 1 2 5
出力
NO
$1 \ 2$ からなる辺は三つの三角形に共有されているため、向き付け不能である。
サンプル3
入力
18 1 2 4 2 4 6 2 3 6 3 6 7 1 3 7 1 4 7 4 5 6 5 6 8 6 7 8 7 8 9 4 7 9 4 5 9 1 5 8 1 2 8 2 8 9 2 3 9 3 5 9 1 3 5
出力
YES
トーラスと呼ばれる曲面の三角形分割であり、向き付け可能である。
同じ頂点や辺が登場してしているが、これは正方形の対辺を同じ向きで貼り合わせた図形上の三角形分割を表している。
本来はトーラスを図示するべきであるが、簡単のために展開図の上に図示した。
サンプル4
入力
6 1 2 3 2 3 5 3 4 5 4 5 6 2 4 6 1 2 6
出力
NO
メビウスの帯の三角形分割である。メビウスの帯は向き付け不能である。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。