## Secret Room

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

Two 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.

### Output

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(√2 - 1) = 1.449747...

(Try calculating it! Please don't try coordinate geometry :P)

### Diagram

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Feb 15, 2009

**Author:** hansonw1

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

hansonw1on Feb 22, 2009 - 3:00:42 pm UTC Re: Re: Accepted: 0?bbi5291on Feb 16, 2009 - 1:16:15 am UTC Tricky problemSourSpinachon Feb 16, 2009 - 4:50:53 pm UTC Re: Tricky problemhansonw1on Feb 15, 2009 - 4:36:44 am UTC Visualizer(It is pretty picky with how you input your data - use the same format as the sample input)