Zadanie

Táto úloha sa dá nahradiť riešením sady conditions_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Mišovi Štrbovi na

Žaba je perfekcionista. Veď sa len pozrite na jeho vlasy. Každý začína a končí presne tam, kde má, každý má svoje miesto a žiaden nie je navyše. Okrem toho je Žaba zdravotník1. A čo robí zdravotník? Lepí leukoplasty, ako keby sme nemali vlastné ruky. Na každú ranu dva, lebo jeden proste nestačí.

Keďže je Žaba perfekcionista, potrebuje presne vedieť, akú plochu na koži jeho pacienta pokrývajú práve nalepené leukoplasty. Práve sa zaoberá nejakými zložitými paralelnými algoritmami2, na toto nemá čas a preto potrebuje aby ste mu s tým pomohli vy.

Úloha

Dostanete zadané pozície rohov dvoch leukoplastov. Musíte ich načítať zo vstupu. Máte napísať program, ktorý zistí a vypíše, koľko veľa (aký obsah) pacientovej kože je zalepenej. V prípade, že sa leukoplasty prekrývajú, oblasť, na ktorej sa prekrývajú zarátajte len raz.

Každý leukoplast je obdĺžnik v štvorcovej sieti, ktorého strany sú rovnobežné s osami x a y (skrátka, obyčajný rovný obdĺžnik).

Vstup

Vstup sa nachádza na štandardnom vstupe. Na jeho načítanie môžete použiť v Pascale funkciu readln(premenna), v Pythone funkciu premenna=input() a v C++ funkciu cin >> premenna.

Vstup sa skladá z dvoch riadkov, každý popisuje jeden leukoplast. Na prvom riadku sa nachádzajú súradnice ľavého dolného (dve čísla – \(x\)-ová a potom \(y\)-ová súradnica) a pravého horného rohu (ďalšie dve čísla – opäť najskôr \(x\)-ová a potom \(y\)-ová súradnica) prvého leukoplastu. Na druhom riadku sa nachádzajú súradnice rohov druhého leukoplastu v rovnakom formáte.

Všetky súradnice sú väčšie (alebo rovné) ako 0 a menšie ako \(1\,000\).

Výstup

Výsledok, teda obsah kože zakrytej leukoplastami, vypíšte na štandardný výstup, v Pascale na to slúži funkcia writeln(vysledok), v Pythone print(vysledok) a v C++ cout << vysledok.

Nezabudnite za číslom dať koniec riadka. writeln() a print() to za vás spravia automaticky, v C++ musíte napísať ešte cout << endl.

Príklady

Input:

1 1 8 4
8 4 14 8

Output:

45

Leukoplasty sa vôbec neprekrývajú, preto je výsledkom súčet ich obsahov.

Input:

0 0 20 20
5 5 15 15

Output:

400

V tomto prípade sa druhý leukoplast celý nachádza v prvom. Preto do celkového povrchu nepridáva žiadnu plochu. Obsah prvého leukoplastu je 400.

Input:

1 1 5 12
3 11 13 14

Output:

72

Prvý obdĺžnik má obsah 44, druhý má obsah 30. Avšak prekrývajú sa na ploche, ktorá má obsah 2. Preto celková plocha, ktorú pokrývajú je 44 + 30 - 2 = 72.

  1. Síce len pre dievčatá, ale to je teraz vedľajšie↩

  2. A popritom čaká, kým mu kuriér prinesie O(log n) počítačov…↩

Ak by sme našli obsah prieniku obdĺžnikov1, riešenie by bolo jednoduché. Sčítali by sme obsahy obdĺžnikov a odrátali obsah ich prieniku, keďže ten sme zarátali dvakrát.

Ako na obsahy obdĺžnikov?

V prvom rade musíme vedieť, ako zrátať obsahy našich obdĺžnikov. Tie vypočítame ako súčin šírky a výšky, ktoré vieme spočítať rozdielom súradníc. Výšku vyrátame ako súradnicu hornej strany mínus súradnicu dolnej, šírku ako súradnicu pravej strany mínus súradnicu ľavej).

Už teda vieme, ako zistíme zo súradníc obdĺžnika jeho obsah. No aj prienik našich obdĺžnikov je len obdĺžnik. Zrátať ho teda môžeme rovnako, stačí len zistiť jeho súradnice.

Ach, prienik, kde si?

Jednou možnosťou bolo začať veľa kresliť a postupne nájsť všetky možnosti, ako môže prienik vyzerať – prienik neexistuje, prenikajú sa rohmi, stranami, jeden obdlžnik je celý vo vnútri toho druhého… Rozlíšiť medzi týmito možnosťami sa síce dalo pomocou komplikovaných if-ov, bolo však ťažké nezabudnúť nejakú možnosť. Pokúsime sa teda nájsť riešenie, ktoré je oveľa všeobecnejšie.

Keby sme porovnali ľavé strany obdĺžnikov, tak vieme povedať, že prienik nebude ohraničený tou viac naľavo. To znamená, že určite bude napravo od oboch ľavých strán. Ak teda prienik existuje, tak jeho ľavá strana je na rovnakej súradnici ako pravšia z ľavých strán štvorcov, teda tá, čo má vačšiu \(x\) súradnicu.

Rovnakú úvahu môžeme zopakovať pre dolné strany – dolná strana prieniku je na rovnakej súradnici ako hornejšia z dolných strán štvorcov, teda tá, čo má väčšiu \(y\) súradnicu.

Pre horné a pravé strany vieme spraviť niečo podobné, akurát zrkadlovo otočené. Horná a pravá strana našeho prieniku musí byť na súradnici nižšej hornej strany (menšia \(y\) súradnica) a ľavšej pravej strany (menšia \(x\) súradnica) našich štvorcov.

Je tu ale malý problém – čo ak obdĺžniky nemajú prienik? V podmienkach predsa rátame s tým, že prienik existuje. V takom prípade sa nám stane akurát to, že výška alebo šírka prieniku nám vyjde menšia alebo rovná nule. Avšak toto si vieme skontrolovať a v takomto prípade vieme, že obsah prieniku je nula.

Na výstup už iba vypíšeme obsah jedného obdĺžnika plus obsah druhého obdĺžnika mínus obsah prieniku.

#include <iostream>
using namespace std;

int main() {
    //suradnice obdlznikov
    int x11,x12,x21,x22,y11,y12,y21,y22;
    cin >> x11 >> y11 >> x12 >> y12;
    cin >> x21 >> y21 >> x22 >> y22;
    //suradnice prieniku
    int px1,px2,py1,py2;
    px1 = max(x11,x21); py1 = max(y11,y21);
    px2 = min(x12,x22); py2 = min(y12,y22);
    int prienik;
    if(px2-px1 <= 0 || py2-py1 <= 0) prienik=0;
    else prienik = (px2-px1)*(py2-py1);
    int obsah1 = (x12-x11)*(y12-y11),obsah2 = (x22-x21)*(y22-y21);
    cout << obsah1 + obsah2 - prienik << endl;
}
program Hello;
var 
//na obdlzniky 1 a 2
vpravo1, vpravo2, vlavo1, vlavo2, hore1, hore2, dole1, dole2: longint;

//na prienik
vpravoP, vlavoP, horeP, doleP: longint;

//pomocne premmene na vysku - sirku
vyska1, sirka1, vyska2, sirka2, vyskaP, sirkaP: longint; 

//obsahy
obsah1, obsah2, obsahP: longint; 

begin
    //nacitame vstup - ohranicenia oblznikou
    readln(dole1, vlavo1, hore1, vpravo1);
    readln(dole2, vlavo2, hore2, vpravo2);

    //pocitame mozne strany prieniku
    if vlavo1 < vlavo2 then vlavoP := vlavo2
    else vlavoP := vlavo1;

    if dole1 < dole2 then doleP := dole2
    else doleP := dole1;

    if vpravo1 > vpravo2 then vpravoP := vpravo2
    else vpravoP := vpravo1;

    if hore1 > hore2 then horeP := hore2
    else horeP := hore1;

    //pocitanie obsahu prieniku
    vyskaP := horeP - doleP;
    sirkaP := vpravoP - vlavoP;

    obsahP := vyskaP * sirkaP;
    if (vyskaP <= 0) or (sirkaP <= 0) then obsahP := 0;

    //pocitanie obsahu velky obdlznikou
    vyska1 := hore1 - dole1;
    sirka1 := vpravo1 - vlavo1;

    obsah1 := vyska1 * sirka1;

    vyska2 := hore2 - dole2;
    sirka2 := vpravo2 - vlavo2;

    obsah2 := vyska2 * sirka2;

    writeln(obsah1 + obsah2 - obsahP);
end.

  1. Prienik je iba vznešenejší názov pre tú oblasť, kde sa leukoplasty prekrývajú↩

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ť.