Building a wall P27780


Statement
 

pdf   zip

thehtml

Let us use right trapezoids to build a wall. Each trapezoid is defined by four real parameters ℓ, r, y and yr, which indicate the points (ℓ, 0), (ℓ, y), (r, yr), and (r, 0). For instance, adding the trapezoids (1 5 1 3) and (7 11 1 3) into an empty wall produces the figure to the left:

unit=0.45cm

(13,8) linestyle=dashed linecolor=green -(0,1)(13,1) -(1,0)(1,7) (2,0)1 (3,0)2 (4,0)3 (5,0)4 (6,0)5 (7,0)6 (8,0)7 (9,0)8 (10,0)9 (11,0)10 (12,0)11 (0,2)1 (0,3)2 (0,4)3 (0,5)4 (0,6)5 linestyle=solid linecolor=black -(2,1)(2,2) -(2,2)(6,4) -(6,4)(6,1) -(8,1)(8,2) -(8,2)(12,4) -(12,4)(12,1)     (13,8) linestyle=dashed linecolor=green -(0,1)(13,1) -(1,0)(1,7) (2,0)1 (3,0)2 (4,0)3 (5,0)4 (6,0)5 (7,0)6 (8,0)7 (9,0)8 (10,0)9 (11,0)10 (12,0)11 (0,2)1 (0,3)2 (0,4)3 (0,5)4 (0,6)5 linestyle=solid linecolor=black -(2,1)(2,2) -(2,2)(4,3) -(4,3)(4,6) -(4,6)(6,6) -(6,6)(6,3) -(6,3)(8,2) -(8,2)(8,3) -(8,3)(10,3) -(10,3)(12,4) -(12,4)(12,1)

The material of the trapezoids is semifluid, so they adapt to the shape underneath. For instance, adding (3 9 3 0) to the figure to the left produces the figure to the right. Write a program to keep track of the shape of an initially empty wall, with two kind of operations:

  • A’ ℓ ⁠ ⁠ r ⁠ ⁠ y⁠ ⁠ yr, to add a trapezoid as already explained.
  • Cx, to consult the current height of the wall at the abscissa x.

Input

Input consists of several cases, each one with the number of operations n, followed by those operations. Assume 1 ≤ n ≤ 105, that all given parametres are real numbers between 0 and ‍104, ℓ < r, and that every x is different to all previous ℓ and r.

Output

For every ‘C’ operation, print the height at x with three digits after the decimal point. The input cases do not have precision issues.

Public test cases
  • Input

    8
    A 1 5 1 3
    C 3
    A 7 11 1 3
    C 10
    A 3 9 3 0
    C 4
    C 6.5
    C 1000
    
    3
    A 0 10000 0 10000
    A 1.2 3.4 100.7 23.42
    C 2.789
    
    1
    C 10
    

    Output

    2.000
    2.500
    5.000
    1.250
    0.000
    47.672
    0.000
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++ Rust