Secret Room

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type

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, W and H (W,H \le 10\,000) representing the width and height of the room.
Then, an integer N \le 50, representing the number of laser beams.
For each laser beam:
4 integers, (x_1,y_1),(x_2,y_2) 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 – (0,0) being the lower left and (W,H) 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 4 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 3.5 \times (\sqrt{2} - 1) = 1.449747\dots
(Try calculating it! Please don't try coordinate geometry :P)

Diagram


Comments

There are no comments at the moment.