Koto Distance

Time Limit : 2 sec, Memory Limit : 131072 KB

問題 A : 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
  • 同一座標に親機は複数存在しない

入出力例

入力例 1

3 9 9
2 2 2
5 5 2
8 8 2

出力例 1

Yes

2番目の親機が提供するWifiの範囲は以下の通りである.

入力例 2

2 7 7
2 2 1
6 6 1

出力例 2

No

入力例 3

3 10 20
5 10 5
2 10 1
8 10 1

出力例 3

Yes

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 2, Tokyo, Japan, 2013-09-21
http://acm-icpc.aitea.net/
http://jag2013summer-day2.contest.atcoder.jp/