Secret RoomHmm, 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!
InputTwo positive integers, W and H (W,H ≤ 10,000) representing the width and height of the room.
Then, an integer N ≤ 50, representing the number of laser beams.
For each laser beam:
4 integers, (x1,y1),(x2,y2) 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 2-D grid - (0,0) being the lower left and (W,H) the upper right.
OutputThe radius of the largest circle that could fit without being cut by lasers.
Your answer should be correct to 4 decimal places.
7 7 5 0 0 7 7 0 7 7 0 0 6 7 2 2 0 2 7 5 0 5 7
The exact answer is 3.5(√2 - 1) = 1.449747...
(Try calculating it! Please don't try coordinate geometry :P)
Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 15, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
(It is pretty picky with how you input your data - use the same format as the sample input)