The fall of the House of Usher P68269
The full, setting, and blood-red moon now shone vividly through that once barely-discernible fissure, of which I have before spoken as extending from the roof of the building, in a zigzag direction, to the base…I saw the mighty walls rushing asunder…And the deep and dank tarn at my feet closed sullenly and silently over the fragments of the “House of Usher”.
The moment just before collapsing, the House of Usher had in fact several fissures. Below you can see an example. The first, zigzag fissure, is like the one of the tale. The second and third fissures go straight from the roof to the base. The fourth and fifth fissures follow stranger directions. In all cases, though, the fissures extend from the roof to the base, and are composed of straight segments.
Given the segments, compute all the areas between fissures (six, in the example).
(0,0)(0,1)15 (0,0)(1,0)60 (60,15)(0,-1)15 (60,15)(-1,0)60
(7,15)0.210(7,15) (4,9)0.211(4,9) (6,7)0.212(6,7) (5,5)0.213(5,5) (7,3)0.214(7,3) (4,0)0.215(4,0)
-1011 -1112 -1213 -1314 -1415
(12,15)0.220(12,15) (12,0)0.221(12,0)
-2021
(18,15)0.225(18,15) (16,0)0.226(16,0)
-2526
(25,15)0.230(25,15) (27,10)0.231(27,10) (25,10)0.232(25,10) (25,8)0.233(25,8) (25,6)0.234(25,6) (27,6)0.235(27,6) (29,6)0.235b(29,6) (25,2)0.236(25,2) (20,12)0.237(20,12) (22,4)0.238(22,4) (23,0)0.239(23,0)
-3031 -3132 -3233 -3334 -3435 -3535b -35b36 -3637 -3738 -3839
(45,15)0.240(45,15) (42,14)0.241(42,14) (42,10)0.242(42,10) (46,9)0.243(46,9) (50,11)0.244(50,11) (46,12)0.245(46,12) (45,11)0.246(45,11) (43,13)0.247(43,13) (53,12)0.248(53,12) (55,9)0.249(55,9) (37,7)0.250(37,7) (35,9)0.251(35,9) (39,11)0.252(39,11) (31,9)0.253(31,9) (40,3)0.254(40,3) (46,6)0.255(46,6) (43,3)0.256(43,3) (50,3)0.257(50,3) (47,0)0.258(47,0)
-4041 -4142 -4243 -4344 -4445 -4546 -4647 -4748 -4849 -4950 -5051 -5152 -5253 -5354 -5455 -5556 -5657 -5758
Input
Input is all integer numbers, and consists of several cases. Every case begins with the length L and the height H of the house’s facade, followed by the number of segments n. Follow the description of n segments, each with four numbers x1, y1, x2 and y2 to indicate that there is an undirected segment from (x1, y1) to (x2, y2). The given segments form correct fissures from the roof to the base. Fissures do not cross themselves nor other fissures, nor even in a single point. Assume 1 ≤ L, H ≤ 106, 0 ≤ n ≤ 105, and 0 < x1, x2 < L. (The first case of the sample input corresponds to the example above.)
Output
For every case, print with one digit after the decimal point all the areas from left to right.
Input
60 15 35 7 15 4 9 4 9 6 7 6 7 5 5 5 5 7 3 7 3 4 0 12 15 12 0 18 15 16 0 25 15 27 10 27 10 25 10 25 10 25 8 25 8 25 6 25 6 27 6 27 6 29 6 29 6 25 2 25 2 20 12 20 12 22 4 22 4 23 0 45 15 42 14 42 14 42 10 42 10 46 9 46 9 50 11 50 11 46 12 46 12 45 11 45 11 43 13 43 13 53 12 53 12 55 9 55 9 37 7 37 7 35 9 35 9 39 11 39 11 31 9 31 9 40 3 40 3 46 6 46 6 43 3 43 3 50 3 50 3 47 0 1000000 1000000 0 17 20 3 10 8 6 15 16 0 6 15 10 8 1 20
Output
82.5 97.5 75.0 116.0 287.0 242.0 1000000000000.0 175.0 165.0
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++