TLE '16 Contest 2 P4 - Harambe's Noble Quest - Olympiads Online Judge

TLE '16 Contest 2 P4 - Harambe's Noble Quest

Points: 15 (partial)

Time limit: 2.0s

Memory limit: 256M

Authors:

d, TT1103

Problem type

Fax McClad defends Harambe the noble Gorilla Knight from Royal Guards.

Harambe, a noble Gorilla Knight, is on a dangerous quest to preserve Gorilla all over the Galaxy. Luckily, he is with Fax McClad, Croneria's most protective bounty hunter.

The two are currently being chased by the Royal Guards (armed with deadly Gorilla guns) in the forests of Radonia. Harambe and Fax McClad are after the Neo Gorilla Cyclone Jet Gorilla Cannon (NGCJGC). Harambe wishes to destroy this devastating interplanetary cannon that can wipe out all Gorilla-kind. Note that only Harambe can destroy this cannon, as he possesses the strength of a mighty Gorilla to do so.

There are many Royal Guards stationed around the cannon. The forests of Radonia can be modelled with a grid with lines $y = a$ $y = a$ and $x = a$ $x = a$ for every integer $a$ $a$ . The NGCJGC is located at the center of the grid, at $(0,0)$ $(0, 0)$ . Harambe's initial location is located at $(x_h,y_h)$ $(x_{h}, y_{h})$ . $T$ $T$ Royal Guards are constantly guarding around the cannon. Each Guard has a sight of length $\ell$ $ℓ$ . That is, the guard can see Harambe if the absolute differences between both their $x$ $x$ and $y$ $y$ coordinates are less than or equal to $\ell$ $ℓ$ . When a Guard sees Harambe, he will instantly annihilate him. Note that a guard can see Harambe even if he is on the outer fringe of his sight.

Note that Harambe can only move vertically and horizontally along grid lines. Additionally, any move he makes must bring him closer to the cannon since in Gorilla culture, it is considered cowardly to increase your distance from the enemy.

Luckily, Fax McClad is there to take out the guards. Fax McClad can take out as many guards as he wishes in an instant. However, Fax McClad is very ~~lazy~~ tired and he wants to do as little work as possible. Thus, it is your job to determine the minimum number of guards that Fax McClad must eliminate in order for Harambe to reach the cannon unscathed. Can you help Fax and Harambe?

Constraints

For all subtasks:

$1 \le T \le 2\,000$ $1 \leq T \leq 2 000$

$0 \le \ell \le 4\,000$ $0 \leq ℓ \leq 4 000$

The absolute value of any coordinate will not exceed $2\,000$ $2 000$ .

Subtask 1 [10%]

$T = 1$ $T = 1$

Subtask 2 [20%]

The absolute value of any coordinate will not exceed $5$ $5$ .

Subtask 3 [30%]

$1 \le T \le 100$ $1 \leq T \leq 100$

The absolute value of any coordinate will not exceed $100$ $100$ .

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line will contain the integers $x_h$ $x_{h}$ and $y_h$ $y_{h}$ , denoting the starting point of Harambe.

The next line will contain $T$ $T$ , denoting the number of Royal Guards.

The next $T$ $T$ lines will contain integers $x$ $x$ , $y$ $y$ and $\ell$ $ℓ$ . $(x,y)$ $(x, y)$ specifies the location of one guard with a maximum sight length of $\ell$ $ℓ$ . No two guards will be at the same position, and no guard can initially see Harambe.

Output Specification

Output an integer indicating the minimum number of guards that Fax McClad must eliminate so that Harambe can destroy the Neo Gorilla Cyclone Jet Gorilla Cannon.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

$\text{[math]}$

In the diagram, the black point represents Harambe's initial starting point and the red points/regions represent the guards and their ranges. Fax must eliminate guard 4 and either guard 1, 2, or 3 so that Harambe can reach $(0,0)$ $(0, 0)$ .

Comments

0

imaxblue commented on Oct. 20, 2016, 11:34 p.m.

can there be negative coordinates?

0

ZQFMGB12 commented on Oct. 20, 2016, 11:42 p.m.

Yes.

0

kobortor commented on Oct. 20, 2016, 10:17 p.m.

what is considered closer? manhattan distance?

0

ZQFMGB12 commented on Oct. 20, 2016, 10:26 p.m.

Yes.