Hmm, now why would someone break into a mundane software company?
After looking at the building blueprints (to place cameras), you've
noticed the suspicious room at the top.
Investigating a little, you find no visible entrance – but there's a
strange humming noise emanating from the room.
Upon asking your manager you are ushered into the conference room where
a confidential meeting seems to be taking place.
It seems that this secret room holds a certain treasure: the
thishasbeencensored
Now, they want to secure this room with lethal green laser beams.
The lasers are very thin, but they have the ability to burn a hole
through an intruder instantly.
The company engineers have built several laser designs, and they'd like
to choose the best one.
To make a laser design effective, they want to minimize the freedom a
thief would have while in the room.
As an estimate, they'd like to find the largest circle that could fit
anywhere without hitting a laser.
Now, doing this by hand would be quite tedious – so write a program to
do it for them!
Input Specification
Two positive integers, and representing the width and
height of the room.
Then, an integer , representing the number of laser beams.
For each laser beam:
integers, representing one laser beam.
A laser beam will travel between those two points (they are guaranteed
to be on the wall).
The room will be modeled as a 2D grid – being the lower left and
the upper right.
Output Specification
The radius of the largest circle that could fit without being cut by
lasers.
Your answer should be correct to decimal places.
Sample Input
7 7
5
0 0 7 7
0 7 7 0
0 6 7 2
2 0 2 7
5 0 5 7
Sample Output
1.4497
The exact answer is
(Try calculating it! Please don't try coordinate geometry :P)
Comments