Gegeven is een lijst van verschillende punten in het vlak, met gehele coördinaten. We zeggen dat een punt \((x,y)\) gedomineerd wordt door \((x',y')\) als \(x\leq x'\) en \(y\leq y'\). Gevraagd is alle punten te zoeken die door geen enkel ander punt in de lijst gedomineerd worden.

Ontwerp en implementeer een algoritme voor dit probleem met tijdscomplexiteit \(\Theta(n \log n)\) dat gebruik maakt van de verdeel-en-heers techniek.

Opgave

Schrijf een klasse MyDomination die de interface Domination¹ implementeert. Je zal ook de klasse Point² nodig hebben.

Deze interface bevat de methode Collection<Point> nonDominated(List<Point> input) die, gegeven de lijst van punten, een collectie naar keuze terug geeft waarin enkel de niet-gedomineerde punten van de input zitten. Je mag de gegeven lijst aanpassen, maar de meegegeven Punten niet. Je mag ook zelf geen nieuwe punten maken via de constructor.

Gebruik eventueel de testklasse SimpleTest³ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.

Tip: je kan de lijst met punten sorteren op de x-waarde door gebruik te maken van de functie Comparator#comparing⁴:

input.sort(Comparator.comparing(Point::getX));