The ICPC world finals will be held in a luxurious hotel with a big ballroom. A buffet meal will be served in this ballroom, and organizers decided to decorate its walls with pictures of past champion teams.
In order to avoid criticism about favouring some of those teams over others, the organizing commitee wants to make sure that all pictures are appropiately illuminated. The only direct way they've found for doing this is ensuring each picture has at least one lightbulb that directly illuminates it.
In this way, the perimeter of the ballroom wall can be divided into illuminated parts (in which pictures may be placed) and dark parts (which are not suitable for placing the pictures).
The ballroom has the shape of a box and contains several lightbulbs. Each lightbulb emits light in all directions, but this light can be blocked by columns. All columns in the ballroom have cylindrical shape and go from the floor to the ceiling, so light cannot pass over or above them. Columns are of course placed so that its circular section is parallel to the ballroom floor. Any given point p
Your task as a helper of the ICPC organization is to examine the blueprints of the ballroom and determine the total length of illuminated sections of the perimeter wall. The blueprint consist of a rectangle indicating a top view of the ballroom, with the lightbulbs and columns marked in it.
Each test case will consist on several lines. The first line will contain four integers: L
The next L
SRC="/ntujudge/problemdata/0832-2.png"
ALT="$ \le$">L
$C \le 10{3}$
-->
C
SRC="/ntujudge/problemdata/0832-2.png"
ALT="$ \le$">103
SRC="/ntujudge/problemdata/0832-2.png"
ALT="$ \le$">X
$Y \le 10{6}$
-->
Y
SRC="/ntujudge/problemdata/0832-2.png"
ALT="$ \le$">106
Input is terminated with <!-- MATH
$L = C = X = Y = 0$
-->
L = C = X = Y = 0
For each test case, output a single line with the total length of the illuminated parts of the perimeter wall. The result must be printed as a real number with exactly four decimal figures. An error of 0.0001 is allowed.
2 1 8 8
6 6
2 6
4 4 2
1 4 7 7
3 3
2 4 1
4 2 1
2 2 1
4 4 1
2 2 9 7
1 2
5 5
3 3 2
7 5 1
0 0 0 0
28.0000
0.0000
25.8214
Migrated from old NTUJ.
South America 2007
| No. | Testdata Range | Score |
|---|