Building a wall P27780


Statement
 

pdf   zip

html

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)green1 (3,0)green2 (4,0)green3 (5,0)green4 (6,0)green5 (7,0)green6 (8,0)green7 (9,0)green8 (10,0)green9 (11,0)green10 (12,0)green11 (0,2)green1 (0,3)green2 (0,4)green3 (0,5)green4 (0,6)green5 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)green1 (3,0)green2 (4,0)green3 (5,0)green4 (6,0)green5 (7,0)green6 (8,0)green7 (9,0)green8 (10,0)green9 (11,0)green10 (12,0)green11 (0,2)green1 (0,3)green2 (0,4)green3 (0,5)green4 (0,6)green5 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.
  • ‘C’ x, 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