15851번 - National Disaster: Two Towers 다국어

Despite its efforts, Indinesia is still regularly hit by uncontrolled forest fires, which causes problems to the local citizens as well as neighbouring countries. Many solutions have been proposed and executed (e.g., dropping water bombs on the burning area), but new hotspots always emerge over time. Nonetheless, Indra, the president of Indinesia, is not yet giving up in solving this problem.

Indinesia has two fire lookout towers located at (x₁, y₁) and (x₂, y₂) where x₁ < x₂ and y₁ < y₂. Moreover, there are N hotspots scattered across the country. The i-th hotspot is a circle with radius r_i and centered at (fx_i, fy_i). A point (x, y) is considered safe if it satisfies all the following properties:

1. x₁ ≤ x ≤ x₂,
2. y₁ ≤ y ≤ y₂,
3. It must not lie strictly inside any burning area; in other words, for all 1 ≤ i ≤ N, the distance of (x, y) to (fx_i, fy_i) should be at least ri.

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 the two towers. A path is considered as safe if and only if all points on the path are safe. Note that "path" as defined in this problem is any continuous and unnecessarily-straight line.

Your task in this problem is to determine whether the two towers are able to communicate properly.

The first line of input contains five integers: x₁ y₁ x₂ y₂ N (-1,000,000 ≤ x₁ < x₂ ≤ 1,000,000; -1,000,000 ≤ y₁ < y₂ ≤ 1,000,000; 0 ≤ N ≤ 1000) in a line denoting the location of the two towers (x₁, y₁) and (x₂, y₂) and the number of hotspots. The next N lines, each contains three integers: fx_i fy_i r_i (-1,000,000 ≤ fx_i, fy_i ≤ 1,000,000; 1 ≤ r_i ≤ 2,000,000) in a line denoting the location of the center of the i-th hotspot (fx_i, fy_i) and its radius of burning area. It is guaranteed that there are no two hotspots at the same (fx_i, fy_i) location. 

The output contains either "YES" or "NO" (without quotes) whether the two towers can communicate properly, in a line.

Explanation for the 1st sample case

For the first sample, the following figure shows one of the safe path connecting the two towers.

Explanation for the 2nd sample case

For the second sample, there is no possible safe path.

Explanation for the 3rd sample case

For the third sample, the following figures show two examples of safe paths connecting the two towers. 

Notice that the points at (10, 15) in the top figure and (10, 30) in the bottom one are safe.