Building a wall P27780
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:
(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.
- ‘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.
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
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Rust