The fall of the House of Usher P68269


Statement
 

pdf   zip

html

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



unit=0.25cm (60,15)

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

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Final
    Date
    2008-10-01