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

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

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Author: hansonw1

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

• (0/1)
Actually it was a bug - when I resubmitted test data the old submission didn't get updated properly.

• (1/1)
Parallel lines are from HELL.

• (1/1)
That's why you use the PUGA (Plachta Universal Geometry Algorithm) for all geometry problems.

• (1/1)
If it helps, you can use this python program to draw test cases. (I used this to check my test data)
(It is pretty picky with how you input your data - use the same format as the sample input)

import Tkinter, os
from Tkinter import *

W, H = map(int, raw_input("Width and height? (W H) ").split(" "))

wscale = 1. * W / max(W, H) * 800
hscale = 1. * H / max(W, H) * 800

def pt(x, y):
x = 5 + 1. * x / W * wscale
y = 5 + hscale - 1. * y / H * hscale
return x,y

root = Tk()

canvas = Canvas(root, width=wscale+10, height=hscale+10)
canvas.pack()

canvas.create_line(pt(0,0), pt(0,H))
canvas.create_line(pt(0,H), pt(W,H))
canvas.create_line(pt(W,H), pt(W,0))
canvas.create_line(pt(W,0), pt(0,0))

N = int(raw_input("Number of lines? (N) "))
for i in range(N):
x1,y1,x2,y2 = map(int, raw_input("Line: (x1 y1 x2 y2) ").split(" "))
canvas.create_line(pt(x1,y1), pt(x2,y2), fill="red")

#If you want, you can draw a circle to see if it lines up
sz = float(raw_input("Radius of the circle? (R) "))

x, y = map(float, raw_input("Centre of the circle (x y)? ").split(" "))
canvas.create_oval(pt(x-sz,y-sz), pt(x+sz,y+sz))

root.mainloop()