Koto 거리

시간 제한2초메모리 제한512 MB

요약

각 접근점이 코토 거리(x 차와 y 차 중 작은 값)가 w_i 이하인 영역을 담당할 때, N개 접근점의 합집합이 W×H 직사각형 전체를 덮는지 판정한다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 구간, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

Koto는 잘 알려진 바둑판 모양의 도시다. 이 도시는 동서 방향으로 $W$ 미터, 남북 방향으로 $H$ 미터 뻗은 직사각형 영역으로 이루어져 있다. 도시의 서쪽 끝에서 $x$ 미터, 남쪽 끝에서 $y$ 미터 떨어진 점은 $(x, y)$ 로 표기한다. 이 도시에 사는 사람들은 예로부터 전해 내려오는 독자적인 문화를 중시하는데, 그중 하나로 Koto 거리라는 특이한 거리 척도가 있다. 두 점 $(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 \le N \le 10^5$
$1 \le W \le 10^5$
$1 \le H \le 10^5$
$0 \le x_i \le W$
$0 \le y_i \le H$
$1 \le w_i \le 10^5$
같은 좌표에 공유기가 여러 개 존재하지 않는다

예제3

예제 1
입력
```
3 9 9
2 2 2
5 5 2
8 8 2
```
예상 출력
```
Yes
```
예제 2
입력
```
2 7 7
2 2 1
6 6 1
```
예상 출력
```
No
```
예제 3
입력
```
3 10 20
5 10 5
2 10 1
8 10 1
```
예상 출력
```
Yes
```