The Department of Defense has been designing autonomous
robots that can infiltrate war zones and other hostile places
in order to carry out missions. Now they want to test their
latest design, the Penetrator1700, and they’ve hired you to
help design the test environment.
The test environment is a rectangular field with some
sensors placed within the field. Each sensor has a certain
radius defining the region within which it can detect a robot.
You want to design the field to have as many sensors as
possible while still permitting a route across the field that
avoids detection.
The field is a region of the coordinate plane defined by
$0\leq x \leq 200$ and
$0 \leq y \leq 300$. The
robot can be modeled by a point that must remain on the field
at all times. It starts at the bottom of the field
($y = 0$) and must end at
the top of the field ($y =
300$), and must not pass within range of any sensor.
There are $N$ sensor
locations given by triples $(x,
y, r)$ of integers, where each $(x, y)$ is a point on the field, and
$r$ is its radius of
detection. The implied sensor circles may overlap, but will
never be tangent with each other nor with the boundary of the
field. All sensors are initially inactive. You must find the
largest value of $k$ such
that if sensors $1, 2, 3, \ldots
, k$ are activated there is a path for the robot across
the field, but no path if the ($k$+1)st sensor is also activated. It
is guaranteed that there is no path if all $N$ sensors are activated.
Input
Input begins with a positive integer $N \leq 200$. Each of the next
$N$ lines has three
spaceseparated integers, representing $x, y, r$ for a sensor, where
$r \leq 300$. All sensors
lie at different $(x,y)$
positions. The first three sample inputs below correspond to
the figure shown.
Output
Output a single integer (which may be $0$) giving the largest $k$ as described above.
Sample Input 1 
Sample Output 1 
6
36 228 58
164 224 58
88 170 42
93 105 42
167 85 58
28 44 58

2

Sample Input 2 
Sample Output 2 
6
36 228 58
28 44 58
164 224 58
88 170 42
93 105 42
167 85 58

3

Sample Input 3 
Sample Output 3 
6
28 44 58
36 228 58
88 170 42
93 105 42
164 224 58
167 85 58

4

Sample Input 4 
Sample Output 4 
3
100 150 101
30 30 10
170 30 100

0
