Given a series of rectangular buildings on a plain field. We view the buildings from the front, this way we receive a two dimensional projection where the countours of buildings overlap on certain places. In figure 1 you can view an example of 5 buildings (colored in blue). We want to calculate the common contour of all buildings, this is illustrated in figure 1 by a red dashed line, we call this contour skyline.

A building is represented by a tuple(x_start, x_end, height) of 3 elements the first is the start x-value, the second is the end x-value and the third is the height of the building. A skyline point is represented by a tuple(x, height) of 2 elements the first is the x-value and the second is the height. The second tuple is used to represent the skyline. A skyline is a list of skyline points where every \(x\)-value is linked to a height change in the contour. The skyline in figure 1 is represented in a list in the following way:

\[[(2, 18), (12, 0), (17, 15), (22, 28), (29, 5), (30, 0)]\]

The skyline starts at the most left coordinate of the leftmost building, on the height of this building, and ends with the rightmost coordinate, and height 0. The \(x\)-coordinates of the consecutive skyline points are strictly ascending and the skyline doesn’t contain redundant points, this means that there is exactly one point for every height change.

It’s required to design a devide and conquer algorithm. You can test every required function separately on Dodona.

1. Write the function building(large_building: tuple). This function calculates the skyline for 1 building.

2. Write the function skyline(buildings: list). This function contains the devide and conquer algorithm that calculates the skyline by using the functions building and merge. You can leave the function merge empty for now.

3. Implement your own verion of merge(skyline1: list, skyline2). This function should merge 2 skylines into one.

Examples

>>> building((10,  20, 10))
[(10, 10), (20, 0)]
>>> building((40, 50, 10))
[(40, 10), (50, 0)]

>>> skyline([(2, 12, 18), (17, 25, 15), (21, 28, 11), (22, 29, 28), (27, 30, 5)])
[(2, 18), (12, 0), (17, 15), (22, 28), (29, 5), (30, 0)]
>>> skyline([(71, 88, 5), (75, 92, 25), (10, 43, 99), (32, 40, 50), (34, 41, 69), (42, 45, 64), (45, 56, 46), (60, 67, 73), (12, 61, 60), (30, 90, 91), (0, 89, 78)])
[(0, 78), (10, 99), (43, 91), (90, 25), (92, 0)]

>>> merge([(2, 18), (12, 0), (17, 15), (22, 28), (29, 5), (30, 0)],[(4, 20), (11, 5), (17, 11), (25, 20), (30, 5), (31, 0)])
[(2, 18), (4, 20), (11, 18), (12, 5), (17, 15), (22, 28), (29, 20), (30, 5), (31, 0)]