Escape Time

Time Limit: 2 Seconds
Memory Limit: 65536 KB

Consider there is a one floor frame structure.
The roof is supported by several beams and the beams are supported by some columns.
The roof is an `n * m` rectangle.
The main beams are all paralleled to the edges of the roof.
And the main beams are all in the range of the roof.
There are some columns to support the roof or the main beams.
The structure engineers think the structure is not strong enough,
so they add some reinforce bars to connect the columns.
This structure is made by standard structure members.
So the distance between adjacent columns is 1,
the length of each main beam is 1, and the length of each reinforce bar is sqrt(2),
which means the angles between the main beams and the reinforce bars are all 45 degrees.
In fact, every crossing point of the beams is supported by a column,
and between every two adjacent columns, there will be at least one beam.
There may be two or more beams or reinforce bars between two adjacent columns.
The main structure is made by wood, so it is afraid of fire.
The beams and the reinforce bars are easy to burn.
The room now is nearly empty,
the floor and the roof is made by other materials which are hard to burn.
So we can consider that if it catches fire near one of the columns,
the only way fire can spread is along the beams and reinforce bars.
The fire can also spread through the crossing point of the reinforce bars.
If more than 50% of the columns catch fire the whole structure will failed.
Because the materials of the structrue members are not stable,
each structure member has a fire spread speed `s`,
the time for fire spread from one end to the other is the length divide the speed.

Now the owner of this house wants to know if one of the columns catches fire,
for the worst situation how long the maximum time for him to escape is.

#### Input

There are several test cases.

For each test case:

The 1st line contains 2 integers `n, m`, indicating the length and width of the structure. (1 ≤ `n, m` ≤ 20)

The 2nd line contains 1 integer `e` (e < 2500),
indicating the total number of the beams and the reinforce bars.

The next `e` lines, every line contains 4 integer `x1,y1,x2,y2`,
(0 ≤ `x1, x2` ≤ `n`; 0 ≤ `y1, y2` ≤ `m` ),
indicating the position of the beams' or the reinforce bars' two ends,
and 1 real number `s`, indicating the fire spread speed of this structure member.

#### Output

For each test cases, you should print one line contains one real number,
for the worst situation the maximum time can the people in the building escape,
round to 3 digits after decimal point.

#### Sample Input

1 1
6
0 0 1 1 2
0 0 0 1 1
0 0 1 0 1
1 1 0 1 1
1 1 1 0 1
1 0 0 1 2
1 1
6
0 0 1 1 0.5
0 0 0 1 2
0 0 1 0 2
1 1 0 1 2
1 1 1 0 2
1 0 0 1 2

#### Sample Output

0.707
0.500

Author:

**LI, Tierui**
Submit
Status