22435번 - Koto Distance 다국어

Koto は言わずと知れた碁盤の目の街である． この街は東西方向に $W$ メートル，南北方向に $H$ メートルに伸びる長方形の領域によってできている． この街の西端から $x$ メートル，南端から $y$ メートルの点は $(x,  y) $ と記される． ここの街に住む人は古くから伝わる独自の文化を重んじており，その一つにKoto距離という変わった距離尺度がある． 2つの点 $(x_1, y_1)$，$(x_2, y_2)$ の Koto 距離は，min$(|x_1 - x_2|,  |y_1 - y_2|)$ によって定義される．

最近この街全体に Wifi を使えるようにする計画が立ち上がった． 現在の計画では，親機を $N$ 個作ることになっている． $i$ 番目の親機は点 $(x_i,  y_i)$ に設置され，Koto距離が $w_i$ 以下の領域に対して Wifi を提供する．

親機を計画どおり建てた場合に，街の内部及び境界上すべてに Wifi を提供できるかどうかを判定せよ．

なお，Koto距離は一般に三角不等式を満たさないため，距離の公理を満たさないということはここだけの秘密である．

入力は以下の形式で与えられる．

$N$ $W$ $H$

$x_1$ $y_1$ $w_1$

$...$

$x_N$ $y_N$ $w_N$

街の内部および境界上すべてに Wifi を提供できるなら “Yes” を，そうでない場合は “No” を出力せよ．

• $1 ≤ N ≤ 10^5$
• $1 ≤ W ≤ 10^5$
• $1 ≤ H ≤ 10^5$
• $0 ≤ x_i ≤ W$
• $0 ≤ y_i ≤ H$
• $1 ≤ w_i ≤ 10^5$
• 同一座標に親機は複数存在しない