問題一覧 > 通常問題

No.3031 曲面の向き付け

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
5 ProblemId : 11868 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-02 22:39:38

注意

この問題は 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もしくは右上の雲マークをクリックしてアカウントを作成してください。