The planet Cartesia has a perfectly flat surface, on which is a grid of
squares. Each location on Cartesia is associated with a pair of
numbers, (x,y), where x is the number of grid squares north
of the planet's center and y is the number of grid squares east
of the planet's center for the given location. Thus, (2.3,1.5) is
the location 2.3 squares north and 1.5 squares east of the planet's
center.
The inhabitants of this planet, the Cartesians, are very small.
They are so small, in fact, that they could be considered to have
no width, much like a point does in Earth-style geometry.
At the center of the planet is a radioactive source with no width as
well. This source emits radiation which is harmful to the Cartesians,
even in the tiniest quantities. The radiation spreads in straight
lines outwards from the source along the surface of the planet.
Fortunately for the Cartesians, there are naturally-occuring trees on
the planet which can block the harmful radiation. Trees, unlike all
else on Cartesia, have a given radius, being perfectly circular. A
Cartesian is safe from the radiation if, when a straight line segment
is drawn between him/her and the radiation source, the line segment
passes through a tree.
Because of the beneficial nature of trees, Cartesians like to build
their houses where they are shaded by trees. Your task is, given a
single tree on the surface of Cartesia and a house location, to find the
largest distance which a Cartesian can travel in a straight line from
the house while guaranteed protection from the radioactive source.
Note that Cartesians cannot walk through trees.
The first line of input is a single positive integer (n) in decimal
notation which represents the number of input lines to follow. The
next n lines contain 5 numbers in decimal notation separated by
single spaces. The first two numbers (x,y) give the location of the
tree (where x is the number of squares north of the planet center and
y is the number of squares east of the planet center). The third
number (r > 0) gives the radius of the tree. The last two numbers
(u,v) give the location of the Cartesian house (where u is the
number of squares north of the planet center and v is the number of
squares east of the planet center). The radioactive source is at
location (0,0). Neither the house nor the radiation source is inside
the tree.
For each input line, your program must output the furthest distance a
Cartesian may travel from the house in a straight line while still
under protection from the radioactive source. The value output must be
a decimal number with three digits after the decimal point. A leading
zero must be included if and only if the output value is less than
1.000, i.e. 0.123 is a valid output, but
.123 is not. If a Cartesian may not leave the house safely at
all, then output a value of 0.000.
3
5 5 1 12 12
20 0 3 7 -7
-9.6 4.3 2.1 -19.2 7.9
2.400
0.000
3.517
Miguel Revilla
2000-08-22