Gegeven zijn een reeks rechthoekige gebouwen die op een vlakte staan. We bekijken deze gebouwen in vooraanzicht en verkrijgen zo een tweedimensionale projectie waarbij de contouren van de gebouwen op zekere plaatsen overlappen. Figuur 1 toont een voorbeeld met vijf gebouwen (in het blauw). We willen de gemeenschappelijke contour van alle gebouwen samen berekenen, zoals ook aangegeven op de figuur in rode stippellijn, en noemen dit de skyline.

Een gebouw wordt voorgested als een tuple(x_begin, x_einde, hoogte) met 3 elementen het eerste element is de begin x-waarde, het tweede de eind x waarde en de derde waarde is de hoogte. Een skylinepunt wordt voorgesteld door een tuple(x, hoogte) met 2 elementen de eerste is de x-waarde en de 2 de waarde is de hoogte. De tweede tuple wordt gebruikt om de skyline voor te stellen. Deze bestaat uit een lijst van skyline punten die aangeven op welke \(x\)-coördinaat de hoogte \(h\) van de skyline verandert. De skyline uit bovenstaande figuur wordt voorgesteld door de volgende lijst punten:

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

De skyline begint bij de linkercoördinaat van het meest linkse gebouw, op de hoogte van dit gebouw, en eindigt bij de rechtercoördinaat van het meest rechtse gebouw, op hoogte nul. De \(x\)-coördinaten van opeenvolgende skyline punten zijn strikt stijgend en de skyline bevat geen overtollige punten, d.w.z. er komt precies één punt voor enkel daar waar de hoogte effectief verandert.

Het is verplicht om een verdeel-en-heers algoritme te ontwikkelen. Elk van de gevraagde functies kan je apart testen op Dodona, ook als de andere nog niet af zijn.

1. Schrijf de functie (gebouw: tuple). Deze berekent de skyline die hoort bij één gebouw.

2. Schrijf de functie skyline(gebouwen: tuple). Deze bevat het verdeel-en-heers algoritme dat de skyline van een reeks gebouwen berekent door gebruik te maken van de methode gebouw en merge. De methode merge laat je op dit moment nog leeg. Wanneer je indient wordt namelijk een bestaande correcte merge-implementatie ingeplugd. Na deze stap zou je ook moeten slagen voor de tweede categorie testen op Dodona.

3. Voorzie tenslotte een eigen implementatie voor de functie merge(skyline1: list, skyline2: list) die de samenvoeging van twee skylines berekent. Deze volgt de maximale hoogte van beide afzonderlijke skylines. Wanneer je zelf een correcte merge hebt geïmplementeerd, zouden de overige testen op Dodona ook moeten slagen.

Dien na elke stap je oplossing in. Ga pas verder met de volgende stap als de testen voor alle voorgaande stappen slagen.

Voorbeelden

>>> gebouw((10,  20, 10))
[(10, 10), (20, 0)]
>>> gebouw((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)]