ACM RTK - 2. skupina

V ravnini imamo podanih n pravokotnikov. Njihove stranice so vzporedne koordinatnima osema, znane pa so tudi njihove koordinate. Za i-ti pravokotnik sta (x_i1, y_i1) koordinati njegovega spodnjega levega oglišča, (x_i2, y_i2) pa koordinati njegovega zgornjega desnega oglišča. Za vsak par pravokotnikov velja naslednje: bodisi je prvi vsebovan v drugem bodisi je drugi vsebovan v prvem bodisi nimata nobene skupne točke. Ne more se torej zgoditi, da bi se dva pravokotnika delno prekrivala, dotikala ali sekala, lahko pa leži eden v drugem. Poleg tega velja tudi, da obstaja med temi pravokotniki en tak, ki vsebuje vse ostale.

Iz teh omejitev sledi, da lahko pravokotnike uredimo hierarhično glede na to vsebovanost. Primer kaže naslednja slika:

---

Opiši postopek, ki za vsak pravokotnik našteje, kateri so njegovi neposredni podrejeni v tej hierarhiji vsebovanosti.

---