Superposition of many rectilinear skylines P48675


Statement
 

pdf   zip   main.cc   main.py

thehtml

The skyline of a city shows the horizon view of its buildings. In this problem we are dealing with rectilinear skylines such us the ones shown in the figure. Each skyline can be represented by a vector of points [(x0,y0),…,(xn−1,yn−1)] with the following properties:

    xi, yi ≥ 0 ∀ i∈{0,…,n−1}
    xi−1 < xi ∀ i∈{1,…,n−1}
    yi−1 ≠ yi ∀ i∈{1,…,n−1}
    x0 > 0, yn−1 = 0

An empty skyline is represented by an empty vector. A non-empty skyline must have at least two points.

The next figure shows three skylines that are represented by the red points. The top-left skyline is represented by the vector of points:

[(1,2), (4,4), (6,1), (8,0), (10,3), (12,1), (14,0)] 

This problem consists of generating the skyline obtained by the superposition of a sequence of skylines. In the figure, the skyline at the right is obtained by the superposition of the two skylines at the left.

Input

Input will start with the number s of skylines to process, with s≥ 2. Then, each skyline will be represented by its number of points n and its set of points x0 ‍y0 ‍x1 ‍y1 ‍… ‍xn−1 ‍yn−1 (fullfilling the previous properties). All the values are integers.

Output

The output will consist of a line, representing the skyline obtained after the superposition of the given skylines.

Observation

Download the code.cc file: you only have to implement the skyline() function and reuse the skyline_superposition() function from problem P76893.

Public test cases

  • Input

    2
7 1 2 4 4 6 1 8 0 10 3 12 1 14 0
5 2 3 6 2 9 0 11 4 13 0

    Output

    9 1 2 2 3 4 4 6 2 9 0 10 3 11 4 13 1 14 0

  • Input

    4
7 1 2 4 4 6 1 8 0 10 3 12 1 14 0
5 2 3 6 2 9 0 11 4 13 0
2 0 8 10 0
4 3 15 8 4 10 2 12 0

    Output

    7 0 8 3 15 8 8 10 3 11 4 13 1 14 0

  • Input

    4
2 1 1 4 0
2 2 2 3 0
2 5 2 6 0
2 5 1 7 0

    Output

    7 1 1 2 2 3 1 4 0 5 2 6 1 7 0
    • Information
    Author
    Jordi Petit and Jordi Cortadella
    Language
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python