5. Oblepené mesto vzorové riešenie

2
0 7 5 5
7 0 5 5
0 0 5 5

0 0 5 5

2
0 5 5 5
5 0 5 5
0 0 5 5

0 0 5 5

2
2 2 9 9
6 0 7 2
1 1 4 4

1 0 12 11

V tomto popise vzorového riešenia budeme používať nasledovné názvoslovie:

• Nutný obdĺžnik = obdĺžnik, ktorý musíme celý prekryť – určený číslami \(x, y, w, h\) zo vstupu.

• Postačujúci obdĺžnik = najmenší obdĺžnik, ktorý pokrýva nutný obdĺžnik a zároveň spĺňa podmienky zadania – správna odpoveď a teda určený číslami \(x_p, y_p, w_p, h_p\).

• Pumpovací obdĺžnik = riešenie bude vždy spočívať v tom, že začneme s nutným obdĺžnikom a budeme ho rozťahovať až kým nedostaneme postačujúci obdĺžnik. Obdĺžnik v procese rozťahovania budeme volať pumpovací obdĺžnik.

Pozorovanie

Najdôležitejšie pozorovanie v celej tejto úlohe je toto: k správnemu riešeniu sa vždy dostaneme nasledovným spôsobom. Za pumpovací obdĺžnik si najprv zoberieme nutný obdĺžnik. Kým sa pumpovací obdĺžnik čiastočne prekrýva s nejakým plagátom, tak pumpovací obdĺžnik roztiahneme tak, aby ten plagát akurát celý prekrýval. Lepšie je to objasnené na nasledujúcom obrázku:

Po roztiahnutí sa môže stať, že sa pumpovací obdĺžnik začne prekrývať s nejakým ďalším plagátom. Tento postup teda opakujeme až kým sa pumpovací obdĺžnik neprekrýva čiastočne so žiadnym plagátom. Vtedy sa pumpovací obdĺžnik rovná postačujúcemu obdĺžniku.

Pomalé riešenie

Toto riešenie bude spočívať v naivnej implementácii spomenutého pozorovania. Najprv si pumpovací obdĺžnik nastavíme na nutný. Potom prejdeme cez všetky plagáty a zistíme, či sa nejaký z nich čiastočne neprekrýva s pumpovacím obdĺžnikom. Ak áno, tak pumpovací obdĺžnik roztiahneme tak, aby akurát pokrýval daný plagát. Tento postup opakujeme, kým dochádza k nejakým zmenám. Keď prestane dochádzať k zmenám, našli sme správne riešenie.

Objasnime si, čo znamená “roztiahnuť obdĺžnik tak, aby akurát pokrýval daný plagát”. Znamená to vytvoriť taký obdĺžnik, ktorý súčasne pokrýva pôvodný obdĺžnik aj plagát a je zároveň čo najmenší. Vieme ho vypočítať takouto funkciou:

def roztiahni(x1, y1, w1, h1, x2, y2, w2, h2):
    left1 = x1
    right1 = x1 + w1
    top1 = y1
    bottom1 = y1 + h1

    left2 = x2
    right2 = x2 + w2
    top2 = y2
    bottom2 = y2 + h2

    left = min(left1, left2)
    right = max(right1, right2)
    top = min(top1, top2)
    bottom = max(bottom1, bottom2)

    x = left
    y = top
    w = right - left
    h = bottom - top

    return x, y, w, h

Funkcia berie ako argumenty dva obdĺžniky. Prvý je zadaný číslami \(x_1, y_1, w_1, h_1\) a druhý číslami \(x_2, y_2, w_2, h_2\). Výsledkom je obdĺžnik, ktorého ľavý okraj je tam, kde je ľavý okraj “ľavejšieho” z obdĺžnikov, pravý tam kde je okraj “pravejšieho” a podobne pre zvyšné prípady.

Pozrime sa na časovú a pamäťovú zložitosť tohto riešenia. Existujú vstupy, v ktorých sa na začiatku nutný obdĺžnik čiastočne prekrýva len s jedným plagátom. Hneď ako ho pokryje, prekryje sa s jedným ďalším a tak ďalej, až kým postupne pokryje všetky plagáty. V tomto riešení potrebujeme s každým novým pokrytím preiterovať cez všetky plagáty, aby sme zistili, s ktorým sa pumpovací obdĺžnik prekrýva. Keďže postupne pokryjeme všetkých \(n\) plagátov a pri každom potrebujeme preiterovať cez všetkých \(n\) plagátov, časová zložitosť je \(O(n^2)\). Pamäťová zložitosť je \(O(n)\), keďže si potrebujeme pamätať len pozície a rozmery všetkých obdĺžnikov.

Rýchle riešenie

Počet plagátov v tejto úlohe môže byť až \(100\,000\) a tak je predchádzajúce riešenie príliš pomalé. Pokúsime sa ho teda zrýchliť.

Najprv si uvedomme, že na každý plagát narazíme buď sprava, zľava, zvrchu, alebo zospodu (teda: najprv sa pumpovací obdĺžnik s daným plagátom neprekrýva, potom sa pumpovací obdĺžnik roztiahne doľava, čo spôsobí, že sa prekryje s nejakým iným plagátom; v tomto prípade naň narazil sprava).

Ďalej je dôležité si uvedomiť, v akom poradí budeme na jednotlivé plagáty narážať. Majme nejaké dva plagáty. Pravý okraj prvého nech je ďalej od nutného obdĺžnika, ako pravý okraj druhého. Ak na oba tieto obdĺžniky narazíme zľava, tak zaručene musíme najprv naraziť na druhý, až potom na prvý, lebo je ďalej.

Z tohto je zrejmé, v akom poradí budeme na jednotlivé plagáty narážať. Najprv narazíme na tie, ktorých okraje sú bližšie, až potom na tie, ktorých okraje sú ďalej.

Plagáty si teda usporiadame osobitne podľa ľavých, pravých, horných a spodných okrajov. Následne si v každom z týchto usporiadaných polí budeme udržiavať ukazovateľ (index), ktorý určuje, kde sa nachádza daný okraj pumpovacieho obdĺžnika.

Na začiatku budú tieto indexy ukazovať na okraje nutného obdĺžnika.

Ďalej si budeme v každom smere udržiavať ďalší ukazovateľ, ktorý nazvime “naťahovací”. Tieto ukazovatele budeme posúvať vždy, keď sa pumpovací obdĺžnik v niektorom smere čiastočne prekrýva s nejakým plagátom.

Ukazovatele pumpovacieho obdĺžnika budú “dobiehať” naťahovacie ukazovatele. Pri každom posunutí ukazovateľov pumpovacieho obdĺžnika narazíme na okraje nejakého nového plagátu. Skontrolujeme teda, či sa s ním pumpovací obdĺžnik čiastočne neprekrýva a ak áno, tak zase posunieme naťahovacie indexy.

Takýmto spôsobom postupne napumpujeme pumpovací obdĺžnik z nutného na postačujúci a tak nájdeme správne riešenie.

Pozrime sa ešte na časovú a pamäťovú zložitosť tohto riešenia. Na začiatku si musíme zoradiť okraje plagátov, čo nám dáva časovú zložitosť najmenej \(O(n \log n)\). V nasledujúcej fáze postupne posúvame ukazovatele. Každý okraj nejakého plagátu však každým ukazovateľom navštívime najviac raz, a tak je časová zložitosť tejto fázy \(O(n)\). Celková časová zložitosť je teda \(O(n \log n)\). Pamäťová zložitosť je \(O(n)\), pretože aj v tomto riešení si musíme len pamätať pozície a rozmery jednotlivých plagátov a nič navyše.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct rect {
    int x1, y1, x2, y2;
};

rect cover(rect r1, rect r2) {
    return {
        min(r1.x1, r2.x1),
        min(r1.y1, r2.y1),
        max(r1.x2, r2.x2),
        max(r1.y2, r2.y2),
    };
}

bool overlap(rect r1, rect r2) {
    int left = r2.x2 - r1.x1;
    int right = r2.x1 - r1.x2;
    int top = r2.y2 - r1.y1;
    int bottom = r2.y1 - r1.y2;
    return !(left <= 0 || right >= 0 || top <= 0 || bottom >= 0);
}

struct edge {
    int pos, rect_index;

    bool operator < (const edge &other) const {
        return pos < other.pos;
    }
};

int main() {
    int n;
    cin >> n;

    vector<rect> rects;
    vector<edge> x_edges;
    vector<edge> y_edges;

    for (int i = 0; i <= n; i++) {
        int x, y, w, h;
        cin >> x >> y >> w >> h;

        rect r = {x, y, x+w, y+h};
        rects.push_back(r);
        x_edges.push_back({r.x1, i});
        x_edges.push_back({r.x2, i});
        y_edges.push_back({r.y1, i});
        y_edges.push_back({r.y2, i});
    }

    sort(x_edges.begin(), x_edges.end());
    sort(y_edges.begin(), y_edges.end());

    rect target = rects.back();

    rect bounding_idx = {
        (int)(lower_bound(x_edges.begin(), x_edges.end(), edge{target.x1, -1}) - x_edges.begin()),
        (int)(lower_bound(y_edges.begin(), y_edges.end(), edge{target.y1, -1}) - y_edges.begin()),
        (int)(lower_bound(x_edges.begin(), x_edges.end(), edge{target.x2, -1}) - x_edges.begin()),
        (int)(lower_bound(y_edges.begin(), y_edges.end(), edge{target.y2, -1}) - y_edges.begin()),
    };

    for (rect r: rects) {
        if (overlap(target, r)) {
            target = cover(target, r);
        }
    }

    vector<rect> overlaps;

    do {
        overlaps.clear();

        rect bounding = {
            x_edges[bounding_idx.x1].pos,
            y_edges[bounding_idx.y1].pos,
            x_edges[bounding_idx.x2].pos,
            y_edges[bounding_idx.y2].pos,
        };

        if (bounding.x1 != target.x1) {
            bounding_idx.x1--;
            overlaps.push_back(rects[x_edges[bounding_idx.x1].rect_index]);
        }
        if (bounding.y1 != target.y1) {
            bounding_idx.y1--;
            overlaps.push_back(rects[y_edges[bounding_idx.y1].rect_index]);
        }
        if (bounding.x2 != target.x2) {
            bounding_idx.x2++;
            overlaps.push_back(rects[x_edges[bounding_idx.x2].rect_index]);
        }
        if (bounding.y2 != target.y2) {
            bounding_idx.y2++;
            overlaps.push_back(rects[y_edges[bounding_idx.y2].rect_index]);
        }

        for (rect &r : overlaps) {
            if (overlap(target, r)) {
                target = cover(target, r);
            }
        }
    } while (int(overlaps.size()) > 0);    // kym sa target meni 

    int x = target.x1;
    int y = target.y1;
    int w = target.x2 - target.x1;
    int h = target.y2 - target.y1;

    cout << x << " " << y << " " << w << " " << h << endl;
}