E - Game in Advertisement
Darjeeling
2
s
1024
MB
400
点
問題文
ひよりさんは動画サイトであるパズルゲームの広告を見つけましたが、広告で出題されている問題はクリアできないように思われました。
問題が与えられるので、クリアできるかどうかを判定するプログラムを作成してください。
ゲームのルールは正確には以下のようなものです。
- $H\times W$ の長方形の周上に $2N$ 個の点が配置されている。点 $i$ は座標 $(x_i,y_i)$ 上にあり、色 $c_i$ に塗られている。
- 任意の色 $c$ に塗られている点はちょうど $2$ つ存在するので、それらを1本の線でつなぐ。この線が直線である必要はないが、線が長方形の外に出たり、複数の線が交差してはならない。
- すべての色について、 $2$ つの点が線でつながれている状態になればクリア。
制約
- $1\leq W,H\leq 10^9$
- $1\leq N\leq10^5$
- $0\leq x_i\leq W$
- $0\leq y_i\leq H$
- すべての $i$ について、以下のうち少なくとも $1$ つが成り立つ
- $x_i=0$
- $x_i=W$
- $y_i=0$
- $y_i=H$
- $i\neq j$ならば、$(x_i,y_i)\neq (x_j,y_j)$
- $1\leq c_i\leq N$
- $1\leq c\leq N$ を満たす任意の $c$ について、$c_i=c$ となる $i$ はちょうど $2$ つ存在する
- 入力はすべて整数
部分点
この問題には部分点が設定されている。以下の制約を満たすテストケースに正解した場合 $200$ 点が与えられる。
- $1\leq W,H\leq 100$
- $1\leq N\leq50$
入力
入力は以下の形式で標準入力より与えられます。
$W$ $H$ $N$
$x_1$ $y_1$ $c_1$
$\vdots$
$x_{2N}$ $y_{2N}$ $c_{2N}$
出力
与えられた問題がクリアできるならYes、できないならNoを出力してください。
入力例 1
10 10 4
2 0 1
7 0 4
10 1 2
10 7 3
7 10 1
0 8 2
0 6 3
0 5 4
出力例 1
No
この問題はクリアできませんが、途中まで進めると以下の様になります。
入力例 2
10 7 4
2 0 1
4 7 1
5 0 2
10 0 2
7 7 3
10 3 3
0 6 4
3 7 4
出力例 2
Yes
問題をクリアした状態を具体的に図示すると以下のようになります。