Zadanie

Farmár Bob sa nedávno rozhodol, že si na svoju farmu dá konečne zaviesť inžinierske siete. Už o pár dní sa mu to na záhrade len tak hemžilo robotníkmi kopajúcimi dlhočizné jamy pre rôzne káble a potrubia. Firma, ktorá túto robotu robila, však nanešťastie skrachovala a Boba nechala s rozkopanou záhradou. Bob sa však po záhrade potrebuje pohybovať, musí sa predsa starať o petržlen, baklažán, cibuľku, jahody … Keďže skákanie cez jamy je príliš nebezpečné, obchádzať sa mu ich nechce a zasypávanie všetkých jám by trvalo príliš dlho, zobral Bob niekoľko dosák a položil ich krížom cez niektoré jamy ako mosty.

Po čase však Bob zistil, že niektoré z týchto dosák by sa mu zišli pri oprave plota. Rozhodol sa teda niektoré jamy zasypať, aby tým nejaké dosky uvoľnil. Ale ktoré? Zišlo by sa mu pre každú jamu vedieť, ktoré dosky cez ňu vlastne vedú.

Úloha

Na záhrade je \(n\) jám očíslovaných \(1, 2, \dots, n\) a \(m\) dosák očíslovaných \(1, 2, \dots, m\). Jamy aj dosky budeme pre jednoduchosť považovať za úsečky v rovine. Žiadne dve jamy nemajú spoločný bod, ani žiadne dve dosky nemajú spoločný bod. Navyše platí, že každá doska sa pretína s práve jednou jamou (pod pojmom “pretína sa” myslíme, že úsečky majú práve jeden spoločný bod a tento bod nie je koncovým bodom žiadnej z nich). Na vstupe dostanete zadané pozície všetkých jám aj dosák. Pre každú jamu vypíšte zoznam dosák, ktoré ju pretínajú.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla \(n, m\) (\(1 \leq n, m \leq 50\,000\)) – počet jám a počet dosák. V každom z nasledujúcich \(n\) riadkov je popis jednej jamy. Popis jamy tvoria štyri celé čísla \(x_1, y_1, x_2, y_2\) \((-1\,000\,000 \leq x_1, y_1, x_2, y_2 \leq 1\,000\,000)\), ktoré popisujú to, že daná jama má koncové body \((x_1, y_1)\) a \((x_2, y_2)\). V nasledujúcich \(m\) riadkoch sú popisy dosák, v rovnakom formáte. Jamy aj dosky sú očíslované v poradí, v akom sú uvedené na vstupe.

Formát výstupu

Pre každú jamu (v poradí, ako sú očíslované), vypíšte jeden riadok. Tento riadok má obsahovať čísla dosák, ktoré túto jamu pretínajú, oddelené presne jednou medzerou, vo vzostupnom poradí. V prípade, že jamu nepretína žiadna doska, vypíšte pre ňu prázdny riadok.

Príklad

Input:

3 4
1 -1 1 4
-1 -2 -3 0
4 3 5 0
3 1 -1 1
3 5 -2 2
5 5 4 -4
3 -1 -1 0

Output:

1 2 4

3

Situácia na Bobovej záhrade vyzerá nasledovne (plné čiary sú jamy, prerušované čiary sú dosky):

Pretínanie úsečiek

Kľúčovou časťou tejto úlohy je zisťovanie, či sa dve úsečky pretínajú. Dve úsečky \(AB\) a \(CD\) sa pretínajú vtedy a len vtedy, keď úsečka \(AB\) pretína priamku \(CD\) a súčasne úsečka \(CD\) pretína priamku \(AB\). To, že úsečka \(CD\) pretína priamku \(AB\) vlastne znamená, že body \(C\) a \(D\) ležia v opačných polrovinách vzhľadom na priamku \(AB\). A to vieme ľahko skontrolovať pomocou vektorového súčinu1 tak, že skontrolujeme, či majú súčiny \((B - A) \times (C - A)\) a \((B - A) \times (D - A)\) opačné znamienka (notáciou \(Y - X\) tu myslíme vektor z \(X\) do \(Y\)). Keďže nás zaujíma iba pretínanie vo vnútorných (nie koncových) bodoch úsečiek, budeme vyžadovať, aby oba vektorové súčiny boli nenulové. To, či úsečka \(AB\) pretína priamku \(CD\) overíme úplne rovnako.

#include <bits/stdc++.h>
using namespace std;
typedef double cislo;

struct vektor {
  cislo x, y;
  
  vektor(cislo xx = cislo(0), cislo yy = cislo(0)) : x(xx), y(yy) {
  }
  
  vektor operator-(vektor prava_strana) {
    return vektor(x - prava_strana.x, y - prava_strana.y);
  }
  
  cislo operator*(vektor prava_strana) {     //vektorovy sucin
    return x * prava_strana.y - y*prava_strana.x;
  }
};

int signum(cislo a) {     //vrati "znamienko" cisla
  if(a < 0)return -1;
  if(a > 0)return 1;
  return 0;
}

struct usecka {
  vektor zaciatok, koniec;
};

bool pretina_priamku_usecky(usecka *u, usecka *p) {      //pretina usecka u priamku, na ktorej lezi usecka p?
  vektor v = p->koniec - p->zaciatok;
  return signum(v * (u->zaciatok - p->zaciatok)) * signum(v * (u->koniec - p->zaciatok)) == -1;
}

bool pretinaju_sa(usecka *u1, usecka *u2) {
  return pretina_priamku_usecky(u1, u2) && pretina_priamku_usecky(u2, u1);
}

Jednoduché riešenie

Keď už vieme v čase \(O(1)\) overovať, či sa dve úsečky pretínajú, ľahko napíšeme riešenie s časovou zložitosťou \(O(n \cdot m)\) – pre každú jamu sa pozrieme na všetky dosky a tie, ktoré pretína, vypíšeme.

Vzorové riešenie

Dá sa to však aj rýchlejšie, konkrétne v čase \(O((n+m) \log (n+m))\). Použijeme techniku s názvom zametanie, ktorá sa v geometrii v rôznych obmenách používa pomerne často.

Pre jednoduchosť budeme chvíľu predpokladať, že na vstupe sa nevyskytujú zvislé úsečky. Nakoniec si ukážeme, ako sa vieme vysporiadať aj s nimi.

Vezmeme myslenú zvislú priamku (ďalej ju budeme volať zametacia priamka), ktorú na začiatku umiestnime dostatočne ďaleko naľavo, tak aby bola naľavo od všetkých úsečiek, ktoré sme dostali na vstupe. Postupne posúvame zametaciu priamku doprava, až kým ju nedostaneme napravo od všetkých úsečiek na vstupe. Počas tohto posúvania si vo vhodnej dátovej štruktúre udržiavame zoznam úsečiek, ktoré momentálne zametaciu priamku pretínajú, usporiadaný podľa \(y\)-ovej súradnice bodu pretnutia (teda úsečka, ktorej priesečník s našou priamkou je najnižšie, bude v zozname prvá a úsečka, ktorá zametaciu priamku pretína najvyššie bude posledná). Keďže v skutočnosti nás zaujímajú iba momenty, keď sa niečo sa deje s týmto zoznamom, stačí nám postupne odsimulovať všetky udalosti, pri ktorých sa zoznam mení (pohyb priamky medzi týmito udalosťami je aj tak nuda).

Zoznam sa bude meniť pri troch druhoch udalostí:

  1. Zametacia priamka ,,narazila’’ na ľavý koniec nejakej novej úsečky. Pri tejto udalosti treba danú úsečku pridať do zoznamu na správne miesto, keďže odteraz bude našu priamku pretínať aj ona.

  2. Zametacia priamka ,,narazila’’ na pravý koniec nejakej úsečky. Vtedy treba danú úsečku zo zoznamu vymazať, keďže odteraz už zametaciu priamku pretínať nebude.

  3. Zametacia priamka ,,narazila’’ na priesečník dvoch úsečiek. Vtedy treba tieto dve úsečky v zozname vymeniť, keďže tá, ktorá doteraz pretínala zametaciu priamku nižšie ju bude odteraz pretínať vyššie a naopak.

Na to, aby sme udalosti mohli spracúvať, musíme, samozrejme, vedieť, kedy nastanú. Za týmto účelom budeme mať haldu (alebo inú prioritnú frontu), na ktorej vrchu bude prvok s najnižšou \(x\)-ovou súradnicou. Do tejto haldy budeme dávať všetky budúce udalosti, o ktorých už vieme, kedy nastanú. Z nej budeme vždy vedieť vybrať najbližšiu udalosť, ktorú máme spracovať.

Už pri načítaní vstupu vieme povedať, kedy (teda pri akej \(x\)-ovej súradnici zametacej priamky) nastanú udalosti prvých dvoch druhov. Tieto udalosti si teda môžeme rovno nasypať do haldy. S udalosťami tretieho typu bude trochu väčší problém, keďže na začiatku netušíme, kde sa jednotlivé úsečky pretínajú. Našťastie nás nič nenúti hádzať všetky tieto udalosti do haldy hneď na začiatku, môžeme ich tam pridávať ,,za behu’’. Jediným obmedzením je, že každú udalosť musíme do haldy pridať skôr, než nastane (inak by sme nevedeli, že ju máme odsimulovať).

Všimnime si, že keď zametacia priamka ide naraziť na priesečník dvoch úsečiek, tesne predtým sú tieto úsečky v zozname úsečiek pretínajúcich zametaciu priamku hneď vedľa seba. Ak by sme teda pri každej zmene zoznamu celý tento zoznam prešli a pre každú dvojicu susedných úsečiek skontrolovali, či sa niekedy v budúcnosti nepretnú (a ak áno, pridali by sme túto udalosť do haldy), určite by sme žiaden priesečník nevynechali. To by, samozrejme, bolo dosť neefektívne, keďže niektoré dvojice úsečiek by sme takto zbytočne kontrolovali veľakrát. V skutočnosti sa nám stačí po každej zmene v zozname pozrieť na tie dvojice úsečiek, ktoré pred zmenou neboli susedné a po zmene sú. Konkrétne:

  1. Po pridaní úsečky do zoznamu sa treba pozrieť, či sa pretne so svojím spodným susedom (ak nejakého má) a či sa pretne s vrchným susedom.

  2. Po zmazaní úsečky zo zoznamu sa treba pozrieť, či sa jej niekdajší susedia (ktorí odteraz susedia navzájom) pretnú.

  3. Po výmene dvoch úsečiek sa treba pozrieť, či sa tieto dve úsečky pretnú so svojimi novými susedmi (tá, ktorá bola pred výmenou nižšie, má teraz nového horného suseda a tá, ktorá bola vyššie, má nového spodného suseda).

Pri spracovaní ľubovoľnej udalosti sa teda pozrieme na \(O(1)\) (jednu alebo dve) novovzniknutých dvojíc susedných úsečiek. Keď o nejakej dvojici zistíme, že sa pretne, poznačíme si to. Ak sme navyše doteraz o tomto priesečníku nevedeli, pridáme ho do haldy. Takýmto spôsobom zaručene nevynecháme žiadnu udalosť, ani žiadnu nespracujeme dvakrát. Navyše popri tom nájdeme všetky priesečníky, čo je presne to, čo potrebujeme.

Zvislé úsečky

Ostáva ešte doriešiť niekoľko detailov. Prvým z nich sú zvislé úsečky. Tie môžeme ošetriť napríklad tak, že zavedieme štvrtý typ udalosti: ,,narazenie’’ zametacej priamky na zvislú úsečku. O týchto udalostiach vieme už po načítaní vstupu povedať, kedy nastanú. Spracovať ich môžeme tak, že v zozname úsečiek pretínajúcich zametaciu priamku binárne vyhľadáme prvú a poslednú úsečku, ktorá danú zvislú úsečku pretína a pre všetky úsečky v zozname medzi nimi si poznačíme priesečník. Zoznam pritom nemeníme, keďže hneď, ako sa zametacia priamka pohne, zoznam sa vráti do pôvodného stavu.

Súčasné udalosti

Druhým problémom je, čo budeme robiť, keď naraz nastane viac ako jedna udalosť. Odpoveď je jednoduchá: odsimulujeme ich jednu po druhej, v ľubovoľnom poradí. Keďže máme zaručené, že úsečky sa pretínajú vždy len vo vnútorných bodoch a v žiadnom bode sa nepretínajú viac ako dve úsečky, udalosti nastávajúce naraz sa nemôžu ovplyvňovať.

Poloha priesečníka

Tretí detail je, že počas zametania budeme občas potrebovať pre dané dve úsečky zistiť, kde (na akej \(x\)-ovej súradnici) sa pretnú. Už sme si ukázali, ako zistiť, či sa pretnú, neukázali sme si však, ako zistiť kde sa pretnú. Priesečník dvoch úsečiek (ak existuje) je priesečník priamok, na ktorých tieto úsečky ležia. Rovnice týchto priamok vieme zapísať v tvare \(a_1 x + b_1 y + c_1 = 0\) a \(a_2 x + b_2 y + c_2 = 0\). Ak \((x, y)\) je ich priesečník, potom musia \(x\) a \(y\) spĺňať rovnice oboch priamok. Máme teda sústavu dvoch rovníc o dvoch neznámych, ktorej riešením dostaneme

\[x = \frac{b_1 c_2 - b_2 c_1}{b_2 a_1 - b_1 a_2} \text{.}\]

Ak máme úsečku zadanú jej koncovými bodmi \((x_1, y_1), (x_2, y_2)\), parametre \(a, b, c\) jej rovnice vieme dopočítať tak, aby jej oba z bodov \((x_1, y_1)\) aj \((x_2, y_2)\) vyhovovali a dostaneme niečo ako

\[a = y_2 - y_1 \text{,}\] \[b = x_1 - x_2 \text{,}\] \[c = -(a x_1 + b y_1) \text{.}\]

Dátová štruktúra zoznamu

Štvrtým (a najväčším) detailom je voľba vhodnej dátovej štruktúry pre zoznam úsečiek pretínajúcich zametaciu priamku. Vhodnou štruktúrou sa ukazujú byť vyvažované binárne vyhľadávacie stromy (v angličnite Binary Search Trees, skratka BST). Tie nám totiž umožňujú mať usporiadaný zoznam prvkov, v ktorom sa dá vyhľadávať, pridať prvok na ľubovoľnú pozíciu aj zmazať ľubovoľný prvok v čase \(O(\log N)\). V C++ sú vyhľadávacie stromy implementované v std::set a táto implementácia sa dá v riešení použiť, je to však dosť bolestivé a silno neodporúčané. Problém je v tom, že sete treba povedať, ako má prvky porovnávať a to sa v našom prípade v čase mení – vždy, keď zametacia priamka prejde nejakým priesečníkom. Preto je veľmi náročné udržať set v konzistentnom stave.

Lepšia voľba je napísať si vlastný BST, na naše účely sa dobre hodí napríklad treap2 s implicitnými kľúčmi. Táto dátová štruktúra sa správa v princípe ako obyčajné pole (teda prvky sú číslované indexami \(0, 1, \dots, N-1\)) s tým rozdielom, že prečítanie prvku na danom indexe trvá čas \(O(\log N)\) namiesto obvyklých \(O(1)\) pri poli. Na oplátku nám však umožňuje nasledujúce operácie:

  • Vymazanie prvku z daného indexu v čase \(O(\log N)\) (ostatné prvky sa automaticky prečíslujú).

  • Vloženie prvku na daný index v čase \(O(\log N)\) (ostatné prvky sa automaticky prečíslujú).

  • Ak si zapamätáme referenciu (pointer) na niektorý prvok, vieme neskôr v čase \(O(\log N)\) zistiť, aký má index (aj ak sa index medzičasom zmenil). To sa nám obzvlášť hodí pri udalostiach 3. typu (vieme si zapamätať, ktoré dva prvky budeme chcieť vymeniť a keď daná udalosť nastane, vieme ich efektívne nájsť).

  • Ak sú v nejakom momente všetky prvky zoznamu podľa niečoho usporiadané, vieme v ňom vďaka stromovej štruktúre binárne vyhľadávať v čase \(O(\log N)\), rovnako ako v obyčajnom poli.

Presnosť

Posledný detail je presnosť výpočtov. Jednou z možností je nenechať nič na náhodu a všetko počítať v racionálnych číslach. Druhá, na implementáciu jednoduchšia možnosť je použiť reálnu aritmetiku. Vtedy ale treba použiť typ premennej s dostatočnou presnosťou (v C++ v závislosti od implementácie mohol stačiť double, alebo mohlo byť nutné použiť long double).

Odhad zložitosti

Zamyslime sa, koľko udalostí budeme musieť počas zametania spracovať. Keďže na vstupe je \(n + m\) úsečiek, udalostí prvého druhu bude najviac \(n+m\), rovnako udalostí druhého a štvrtého druhu. Keďže každá doska sa pretína s práve jednou jamou, úsečky na vstupe majú dokopy \(m\) priesečníkov, teda budeme mať \(m\) udalostí tretieho druhu. Dokopy teda máme \(O(n+m)\) udalostí. Udalosti prvých troch druhov vieme spracúvať v čase \(O(\log(n+m))\) (vybranie udalosti z haldy, konštantne veľa operácii so zoznamom úsečiek pretínajúcich zametaciu priamku, prípadné pridanie konštantného počtu udalostí na haldu). S udalosťami štvrtého druhu (zvislými úsečkami) je to trochu horšie. Ak má daná zvislá úsečka \(p\) priesečníkov, jej spracovanie môže trvať až \(O((p+1) \log(n+m))\). Vieme však, že na vstupe je dokopy \(m\) priesečníkov, teda súčeť \(p\)-čiek pre všetky zvislé úsečky dokopy je najviac \(m\). To znamená, že spracovanie všetkých udalostí štvrtého druhu nám zaberie dokopy \(O((n+m) \log (n+m))\) času. Spracovanie ostatných udalostí tiež trvá \(O((n+m) \log (n+m))\), teda aj celé zametanie bude trvať \(O((n+m) \log (n+m))\). Načítanie vstupu a nahádzanie udalostí do haldy trvá \(O((n+m) \log (n+m))\) času, vypisovanie výstupu trvá tiež \(O((n+m) \log (n+m))\) (lebo ho pred vypísaním potrebujeme triediť), celková časová zložitosť nášho algoritmu je teda \(O((n+m) \log (n+m))\).

Pamäťová zložitosť je \(O(n+m)\).

struct uzol;
typedef pair<uzol*, uzol*> puu; 

//časť zdrojového kódu, ktorá je uvedená v predošlom listingu, už neuvádzame. Výnimkou
//je definícia štruktúry usecka, do ktorej sme nejaké veci pridali.

struct usecka {
  vektor zaciatok, koniec;
  int id;
  vector<usecka*> koho_pretinam;
  
  usecka(vektor z, vektor k, int i = -1) : zaciatok(z), koniec(k), id(i) {
    if(make_pair(zaciatok.x, zaciatok.y) > make_pair(koniec.x, koniec.y)) swap(zaciatok, koniec);
  }
  
  bool zvisla() {
    return zaciatok.x == koniec.x;
  }
  
  cislo y_na(cislo x) {
    return (x - zaciatok.x) * (koniec.y - zaciatok.y) / (koniec.x - zaciatok.x) + zaciatok.y;
  }
};

struct priamka {
  cislo a, b, c;
  
  priamka(usecka *u) {
    a = u->koniec.y - u->zaciatok.y;
    b = u->zaciatok.x - u->koniec.x;
    c = 0 - (a*u->zaciatok.x + b*u->zaciatok.y);
  }
};

cislo priesecnik_x(usecka *u1, usecka *u2) {
  priamka p1(u1), p2(u2);
  return (p1.b * p2.c - p2.b * p1.c) / (p2.b * p1.a - p1.b * p2.a);
}


int velkost_podstromu(uzol *u);

struct uzol {
  uzol *lavy, *pravy, *otec;
  usecka *hodn;
  int priorita;
  int podstrom;
  
  uzol(usecka *u = NULL) : hodn(u), lavy(NULL), pravy(NULL), otec(NULL), priorita(rand()), podstrom(1) {
  }
  
  void reinit() {
    lavy = pravy = otec = NULL;
    priorita = rand();
    podstrom = 1;
  }
  
  int update() {
    podstrom = 1 + velkost_podstromu(lavy) + velkost_podstromu(pravy);
  }
  
  void nastav_lavy(uzol *u) {
    lavy = u;
    if(u != NULL) u->otec = this;
    update();
  }
  
  void nastav_pravy(uzol *u) {
    pravy = u;
    if(u != NULL) u->otec = this;
    update();
  }
  
  int index() {
    if(otec == NULL) return velkost_podstromu(lavy);
    int oi = otec->index();
    if(otec->lavy == this) return oi - 1 - velkost_podstromu(pravy);
    return oi + 1 + velkost_podstromu(lavy);
  }
};

int velkost_podstromu(uzol *u) {
  return u == NULL ? 0 : u->podstrom;
}

puu split(uzol *koren, int kde) {
  if(koren == NULL)return puu((uzol*)NULL, (uzol*)NULL);
  if(velkost_podstromu(koren->lavy) >= kde) {
    puu pom = split(koren->lavy, kde);
    koren->nastav_lavy(pom.second);
    return puu(pom.first, koren);
  }
  puu pom = split(koren->pravy, kde - velkost_podstromu(koren->lavy) - 1);
  koren->nastav_pravy(pom.first);
  return puu(koren, pom.second);
}

uzol* merge(uzol *a, uzol *b) {
  if(a != NULL) a->otec = NULL;
  if(b != NULL) b->otec = NULL;
  if(a == NULL) return b;
  if(b == NULL) return a;
  if(a->priorita > b->priorita) {
    a->nastav_pravy(merge(a->pravy, b));
    return a;
  }
  b->nastav_lavy(merge(a, b->lavy));
  return b;
}

uzol* insert(uzol *koren, int kde, uzol *u) {
  if(koren == NULL)return u;
  if(koren->priorita < u->priorita) {
    puu pom = split(koren, kde);
    u->nastav_lavy(pom.first);
    u->nastav_pravy(pom.second);
    return u;
  }
  if(kde <= velkost_podstromu(koren->lavy)) {
    koren->nastav_lavy(insert(koren->lavy, kde, u));
    return koren;
  }
  koren->nastav_pravy(insert(koren->pravy, kde - 1 - velkost_podstromu(koren->lavy), u));
  return koren;
}

uzol* erase(uzol *koren, int kde, bool znic = 1) {
  if(koren == NULL)return NULL;
  int ls = velkost_podstromu(koren->lavy);
  if(kde < ls) {
    koren->nastav_lavy(erase(koren->lavy, kde, znic));
    return koren;
  }
  if(kde > ls) {
    koren->nastav_pravy(erase(koren->pravy, kde - 1 - velkost_podstromu(koren->lavy), znic));
    return koren;
  }
  uzol *res = merge(koren->lavy, koren->pravy);
  if(znic) delete koren;
  else koren->reinit();
  return res;
}

uzol* get(uzol *koren, int kde) {
  if(koren == NULL)return NULL;
  int ls = velkost_podstromu(koren->lavy);
  if(kde < ls)return get(koren->lavy, kde);
  if(kde > ls)return get(koren->pravy, kde - ls - 1);
  return koren;
}

int index_of(uzol *koren, int y, int x) {
  if(koren == NULL)return 0;
  cislo ry = koren->hodn->y_na(x);
  if(y > ry) return index_of(koren->pravy, y, x) + velkost_podstromu(koren->lavy) + 1;
  return index_of(koren->lavy, y, x);
}

enum typ_udalosti{prisla_usecka, odisla_usecka, zvisla_usecka, vymena_useciek};

struct udalost {
  typ_udalosti co;
  usecka *u;
  uzol *n1, *n2;
  
  udalost(typ_udalosti c, usecka* us = NULL, uzol* no1 = NULL, uzol* no2 = NULL) : co(c), u(us), n1(no1), n2(no2) {
  }
};

void pretni(usecka* u1, usecka* u2) {
  u1->koho_pretinam.push_back(u2);
  u2->koho_pretinam.push_back(u1);
}

void over_koliziu(uzol *n1, uzol *n2, 
         priority_queue<pair<cislo, udalost* >, vector<pair<cislo, udalost*> >, greater<pair<cislo, udalost*> > >& halda) {
  if(n1 == NULL || n2 == NULL)return;
  usecka *u1 = n1->hodn, *u2 = n2->hodn;
  if(u1->koho_pretinam.size() > 0 && u2->koho_pretinam.size() > 0)return;
  if(pretinaju_sa(u1, u2)) {
    halda.push(pair<cislo, udalost*> (priesecnik_x(u1, u2), new udalost(vymena_useciek, NULL, n1, n2)));
    pretni(u1, u2);
  }
}

int main() {
  int n, m;
  scanf("%d %d",&n,&m);
  vector<usecka*> objekt;
  priority_queue<pair<cislo, udalost* >, vector<pair<cislo, udalost*> >, greater<pair<cislo, udalost*> > > halda;
  for(int i=0; i<n + m; i++) {
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    usecka *u = new usecka(vektor(x1, y1), vektor(x2, y2), i-n);
    objekt.push_back(u);
    if(u->zvisla()) halda.push(pair<cislo, udalost*> (u->zaciatok.x, new udalost(zvisla_usecka, u)));
    else {
      halda.push(pair<cislo, udalost*> (u->zaciatok.x, new udalost(prisla_usecka, u)));
      halda.push(pair<cislo, udalost*> (u->koniec.x, new udalost(odisla_usecka, u)));
    }
  }
  
  uzol *metla = NULL;
  
  while(!halda.empty()) {
    pair<cislo, udalost*> akt = halda.top();
    halda.pop();
    cislo x = akt.first;
    udalost *ud = akt.second;
    switch(ud->co) {
      case prisla_usecka: {
        int y = ud->u->zaciatok.y;
        int ind = index_of(metla, y, x);
        uzol *cr = new uzol(akt.second->u);
        metla = insert(metla, ind, cr);
        uzol *prev = get(metla, ind-1);
        uzol *nxt = get(metla, ind+1);
        over_koliziu(prev, cr, halda);
        over_koliziu(cr, nxt, halda);
        break;
      }
      case odisla_usecka: {
        int y = ud->u->koniec.y;
        int ind = index_of(metla, y, x);
        metla = erase(metla, ind);
        uzol *prev = get(metla, ind-1);
        uzol *nxt = get(metla, ind);
        over_koliziu(prev, nxt, halda);
        break;
      }
      case zvisla_usecka: {
        int y1 = ud->u->zaciatok.y, y2 = ud->u->koniec.y;
        int i1 = index_of(metla, y1, x), i2 = index_of(metla, y2, x);
        for(int i=i1; i<i2; i++) {
          pretni(get(metla, i)->hodn, ud->u);
        }
        break;
      }
      case vymena_useciek: {
        uzol *n1 = ud->n1, *n2 = ud->n2;
        int i1 = n1->index(), i2 = n2->index();
        metla = erase(metla, i1, false);
        metla = erase(metla, i1, false);
        metla = insert(metla, i1, n1);
        metla = insert(metla, i1, n2);
        uzol *prev = get(metla, i1-1);
        uzol *nxt = get(metla, i2+1);
        over_koliziu(prev, n2, halda);
        over_koliziu(n1, nxt, halda);
        break;
      }
    }
  }
  
  for(int i=0; i<n; i++) {
    vector<int> pom;
    for(int j=0; j<objekt[i]->koho_pretinam.size(); j++) {
      pom.push_back(objekt[i]->koho_pretinam[j]->id+1);
    }
    sort(pom.begin(), pom.end());
    for(int j=0; j<pom.size(); j++) {
      printf("%d", pom[j]);
      if(j+1 < pom.size())printf(" ");
    }
    printf("\n");
    delete objekt[i];
  }
  return 0;
}

  1. viac o vektorovom súčine a jeho využití si môžete prečítať na https://www.ksp.sk/kucharka/skalarny_a_vektorovy_sucin↩

  2. viac o treapoch na https://www.ksp.sk/kucharka/treap↩

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