National Disaster: Two Towers

Time limit2sMemory limit512 MB

Summary

In a rectangle bounded by two towers, decide whether burning circles block every continuous path between the towers, which happens exactly when a connected chain of circles links two opposite walls of the rectangle.

Level: Medium7 of 10
Topics: Geometry, Union-find, Graph, Implementation
Solved: No attempts yet

Problem

Indinesia has two fire lookout towers at $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1 < x_2$ and $y_1 < y_2$ . Across the country there are $N$ hotspots, and the $i$ -th hotspot is a circle with radius $r_i$ centered at $(fx_i, fy_i)$ . A point $(x, y)$ is safe when it satisfies all of the following conditions.

$x_1 \le x \le x_2$ ,
$y_1 \le y \le y_2$ ,
It does not lie strictly inside any burning area. In other words, for every $1 \le i \le N$ , the distance from $(x, y)$ to $(fx_i, fy_i)$ is at least $r_i$ .

The locations of the two towers are guaranteed to be safe. The two towers can communicate properly if and only if there exists a safe path connecting them. A path is safe if and only if every point on it is safe. Here a path is any continuous curve, and it does not need to be straight.

Determine whether the two towers can communicate properly.

Input

The first line contains five integers $x_1$ , $y_1$ , $x_2$ , $y_2$ and $N$ ( $-1000000 \le x_1 < x_2 \le 1000000$ , $-1000000 \le y_1 < y_2 \le 1000000$ , $0 \le N \le 1000$ ), denoting the locations $(x_1, y_1)$ and $(x_2, y_2)$ of the two towers and the number of hotspots. Each of the next $N$ lines contains three integers $fx_i$ , $fy_i$ and $r_i$ ( $-1000000 \le fx_i, fy_i \le 1000000$ , $1 \le r_i \le 2000000$ ), denoting the center of the $i$ -th hotspot and the radius of its burning area. No two hotspots share the same center.

Output

Print "YES" in a line when the two towers can communicate properly, and "NO" otherwise (without quotes).

Hint

The figure below is an example of a safe path connecting the two lookout towers.

Figure showing a safe path example

The figure below is an example of a case where no safe path exists.

Figure showing that no safe path exists

The two figures below show another example of a safe path connecting the two lookout towers. The point (10, 15) in the upper figure and the point (10, 30) in the lower figure are safe.

Upper figure of another safe-path example where the point (10, 15) is safe

Lower figure of another safe-path example where the point (10, 30) is safe

Examples3

Example 1

Input

-15 -10 15 10 5
-20 7 9
-2 3 6
8 -3 4
-1 -8 3
-9 -1 3

Expected output

YES

Example 2

Input

2 10 18 30 3
10 20 5
10 29 5
10 11 5

Expected output

NO

Example 3

Input

2 10 18 30 3
10 20 5
10 25 5
10 10 5

Expected output

YES