Zadanie
Bratislava, hlavné mesto Slovenska, je celkom slušne oblepená. To určite viete, ak ste v nej aspoň raz v živote boli. Billboard sem, billboard tam, plagáty a plagáty. Ale ani jeden nepatrí spoločnosti Kaderníkov Spod Papuče. Jej manažér, Mário, si to tiež všimol a tak sa rozhodol, že jeden plagát svojej spoločnosti predsa len vybaví.
Pochodil celú Bratislavu a nakoniec našiel ideálnu stenu. Bolo na nej už síce zopár plagátov, ale to nevadí. “Veď nejaké môžeme aj prelepiť,” povedal si Mário. V Bratislave je však zakázané prelepiť nejaký plagát čiastočne, a tak je to aj správne, veď je to potom hrozne neestetické. Ak sa má nejaký plagát prelepiť, tak celý!
Teraz Mário nevie, ako má nalepiť plagát Kaderníkov Spod Papuče. Pomôžete mu?
Úloha
Na stene je už umiestnených niekoľko plagátov, ktoré majú tvar obdĺžnikov, ktorých strany sú rovnobežné s osami súradnicovej sústavy. Mário si zaumienil, že plagát svojej spoločnosti musí pokrývať aspoň obdĺžnik \((x, y, w, h)\) (\(x, y\) určujú pozíciu ľavého horného rohu, \(w, h\) určujú šírku a výšku).
Teraz potrebuje nájsť takú obdĺžnikovú plochu na nalepenie plagátu, aby pokrývala aspoň obdĺžnik \((x, y, w, h)\) a zároveň, aby každý iný plagát prekrývala buď celý alebo vôbec.
Keďže spoločnosť Kaderníkov Spod Papuče má len obmedzené financie, Mário chce nájsť najmenší takýto obdĺžnik.
Formát vstupu
Na prvom riadku sa nachádza jedno celé číslo \(n\) (\(0 \leq n \leq 100\,000\)) – počet plagátov na stene.
Na ďalších \(n\) riadkoch sa nachádzajú popisy jednotlivých plagátov. Na \(i\)-tom z týchto riadkov sú štyri celé čísla oddelené jednou medzerou: \(x_i, y_i, w_i, h_i\). Čísla \(x_i, y_i\) určujú súradnice ľavého horného rohu \(i\)-teho plagátu a čísla \(w_i, h_i\) určujú jeho šírku a výšku. Tieto plagáty sa môžu čiastočne aj úplne prekrývať.
Pozor, v tejto úlohe používame súradnicovú sústavu, kde sa \(y\)-ová súradnica zväčšuje smerom dole. Preto určujeme pozíciu ľavého horného rohu.
Pre všetky \(i\) platí \(0 \leq x_i, y_i, w_i, h_i \leq 10^9\).
Na poslednom riadku sa nachádzajú čísla \(x, y, w, h\) oddelené medzerou. Tieto popisujú plochu, ktorá musí byť pokrytá Máriovým plagátom.
Rovnako platí, že \(0 \leq x, y, w, h \leq 10^9\).
Formát výstupu
Vypíšte jeden riadok a na ňom štyri celé čísla oddelené jednou medzerou: \(x_p, y_p, w_p, h_p\), kde \(x_p, y_p\) sú súradnice ľavého horného rohu a \(w_p, h_p\) sú šírka a výška plochy kam nakoniec Mário nalepí plagát svojej spoločnosti.
Príklady
Input:
2
0 7 5 5
7 0 5 5
0 0 5 5
Output:
0 0 5 5
Máriova vysnívaná plocha sa neprekrýva so žiadnym existujúcim plagátom.
Input:
2
0 5 5 5
5 0 5 5
0 0 5 5
Output:
0 0 5 5
Dokonca ani teraz sa neprekrýva so žiadnym existujúcim plagátom.
Input:
2
2 2 9 9
6 0 7 2
1 1 4 4
Output:
1 0 12 11
Cieľová plocha sa prekrýva s prvým plagátom. Ak ho však chceme zahrnúť, nevieme sa vyhnúť prekrytiu s druhým, a tak musíme zakryť aj ten.
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;
}
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.