ZOJ Problem Set - 3372
Macrohard head Bill Hates has recently decided to build the new swimming pool at his villa. He called his designer and asked him to design the pool. Since there are many people in Bill's family, the pool must have several sections of different depths.
Today the construction of the pool is completed. It has the form of a rectangle and consists of several rectangular sections. Sections are separated by the borders, top side of each border is on the ground level. Each section has some depth.
Now Bill wants to fill the pool with water. The water gets to the pool from the source located in some section. It brings s liters of water per minute to the pool. When the section is filled with water, the waters starts to flow to the adjacent sections. The amount of water flowing over the border is proportional to its length. When several adjacent sections are filled, they act as one section, i.e. as if there were no border between them. The water flowing over the outer border of the pool is carried away by a special system of the pipes, thus it leaves the pool.
Bill wants to know, what is the time required to fill the pool, if it's initially empty. Help him!
For example, let the pool be designed as shown on the picture, number in each section specifies its depth in centimeters, source is located in the center section of the pool. Let the amount of water getting from the source be 1000 liters per minute. The center section is filled after 6 minutes and the water starts to flow to adjacent sections. The section on the top left gets 125 liters per minute, the section on the top right gets 250 liters per minute and the section on the bottom gets 375 liters per minute. Another 250 liters per minute flow over the outer borders.
In 8 minutes the section on the top right gets filled. Now it is joined with the center section, their common border length is 10 meters, so 200 liters per minute flows to the section on the top left, and 300 to the section on the bottom. 500 liters per minute flows over the outer pool borders.
Another 5 minutes are required for the bottom section to get filled. Now the bottom section is joined with the main section and they act as the whole. The border length is 12 meters, so now 166.67 liters per minute gets to the top right section. It takes another 6 minutes to fill it completely.
The first line of the input file contains n, x, y, p and s --- the number of sections of the pool, its size x * y in meters, the number of the section where the water source is located, and the number of liters getting out of the source per minute (1 ≤ n ≤ 100, 1 ≤ x, y ≤ 100, 1 ≤ s ≤ 100000).
The following n lines contain descriptions of the sections: each section is described with five integer numbers: x1, y1, x2, y2 and d --- the coordinates of its bottom-left and top-right corner in meters and its depth in centimeters (1 ≤ d ≤ 1000). Sections do not overlap and cover the whole pool.
There are multiple cases. Process to the end of file.
Output a real number --- the number of minutes required to fill the whole pool with water. Your answer must be accurate up to 10-4.
4 3 3 2 1000 0 0 3 1 150 0 1 3 2 200 0 2 1 3 300 1 2 3 3 100
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11