5. Ooo, Vlaky vzorové riešenie

Zadanie

Píše sa rok \(2143\). Presne pred \(100\) rokmi sa človek stal multiplanetárnym druhom, keď prví vesmírni osadníci pristáli na Marse a následne vybudovali kolóniu. Na začiatku ich tam bolo presne \(157\) a každý tak mal dostatok priestoru, keďže pôvodná kapacita prvej kolónie sa šplhala až k číslu \(1223\).

Časom však populácia červenej planéty rástla¹. \(53\%\) terajších obyvateľov pricestovalo zo Zeme alebo z Mesiaca a \(47\%\) sa na Marse už narodilo. Preto už takýchto kolónií existuje niekoľko (rádovo v stovkách). Čoskoro, teda, dôjde k vyrovnaniu pomeru úplných² a polovičných³ “Marťanov”, a veľkosť populácie prekročí \(200\,000\).

Znie to veľmi sľubne a prosperujúco, no obyvateľov Marsu stále ešte obmedzuje pár vecí, medzi ktoré patrí napríklad aj doprava. Na prepravu materiálu, potravín alebo osôb sa v tomto nehostinnom teréne používajú elektrické rovery. Tie majú svoje nevýhody: sú pomalé, často sa kvôli prašnému povrchu kazia, majú relatívne malú nosnosť a, samozrejme, z bezpečnostných dôvodov nepremávajú počas Marťanskej búrky. Preto sa Rada kolónií Marsu, Aliancia štátov pre multiplanetárny život a Medzinárodná rada vesmírnych agentúr rozhodli riešiť dopravu na tejto planéte.

Za najvhodnejší spôsob prepravy osôb a tovaru tu považujú vlaky, premávajúce hermeticky uzavretými podzemnými tunelmi. Tie budú môcť premávať aj počas búrok⁴, uvezú veľa nákladu, nebudú vystavené prašnému prostrediu a budú relatívne rýchle⁵. Okrem toho, odhlasovalo sa, že z bezpečnostných dôvodov⁶ budú všetky tunely vybudované v rovnakej hĺbke, a to znamená, že žiadne dva tunely sa nesmú križovať. V každom tuneli bude premávať práve jeden vlak. Vlaky sú totiž najdrahšou položkou v tomto projekte a preto ich počet, a teda aj počet tunelov, bude čo najnižší. Zároveň ich treba toľko, aby sa bolo možné dostať z ľubovoľnej kolónie do hociktorej inej len použitím vlakov. Ak si teda vlakovú sieť predstavíme ako graf, tak bude vyzerať ako strom, z čoho vyplýva, že počet tunelov bude počet kolónií mínus \(1\).

Plán projektu sa skladal z troch tabuliek:

• V jednej boli spárované identifikačné čísla pozícií s ich súradnicami na mape⁷.

Pozícia	ID pozície
\([0, 0]\)	\(1\)
\([1, 1]\)	\(2\)
\([2, 3]\)	\(3\)

• V druhej boli pozície priradené číslam a názvom kolónií.

ID pozície	ID kolónie	Kolónia
\(1\)	\(1\)	Jablkovo
\(2\)	\(2\)	Hruškovo
\(3\)	\(0\)	Malinovo

• V tretej sa nachádzal zoznam dvojíc čísel kolónií, ktoré je potrebné prepojiť tunelom.

ID kolónie \(a\)	ID kolónie \(b\)
\(1\)	\(2\)
\(0\)	\(2\)

Po pár mesiacoch bol plán projektu hotový a išlo sa stavať, no nastal problém. Druhá tabuľka sa záhadne stratila, a tak sú v projekte len súradnice a prepojenia čísel kolónií. Nevieme ale, ktorá kolónia je na ktorých súradniciach.

Stavebníci teraz nevedia, kde treba stavať. Skúste ale z projektu zachrániť, čo sa dá: navrhnite také riešenie, ktoré teoreticky môže byť pôvodne zamýšľaný plán.

Úloha

Na Marse sa nachádza \(n\) kolónií. Poznáte ich \(n\) celočíselných súradníc \(x, y\), avšak, neviete konkrétne, ktorá pozícia prislúcha ktorej kolónii. Pozície sú navzájom rôzne, a žiadne tri pozície neležia na jednej priamke.

Ďalej máte plán projektu, v ktorom sú zapísané dvojice čísel \(a, b\) označujúce kolónie, medzi ktorými má viesť obojsmerný tunel. Táto vlaková sieť tvorí graf-strom: je teda súvislá a vedie v nej práve \(n-1\) hrán.

Navrhnite, medzi ktorými pozíciami majú viesť tunely tak, aby sa žiadne dva tunely nekrižovali, a aby jednotlivé pozície v nejakom poradí zodpovedali jednotlivým kolóniám.

Vstup

V prvom riadku vstupu sa nachádza číslo \(1 \leq n \leq 1\,000\) udávajúce počet kolónií. Nasleduje \(n - 1\) riadkov. V každom z nich sa nachádzajú dve čísla \(a, b\) hovoriace, že medzi kolóniami \(a\) a \(b\) má byť postavený tunel. Kolónie číslujeme \(0, 1, \ldots, n-1\).

Ďalej nasleduje \(n\) riadkov. V \(i\)-tom z nich sa nachádzajú dve čísla \(x_i, y_i\), súradnice \(i\)-tej pozície nejakej kolónie. Tieto súradnice v absolútnej hodnote nepresiahnu \(10^9\).

Výstup

Na výstup vypíšte \(n - 1\) riadkov. V každom z nich nech je dvojica čísel \(a, b\), ktorá znamená, že medzi \(a\)-tou pozíciou a \(b\)-tou pozíciou má viesť tunel. Pozície číslujeme od \(0\) po \(n-1\).

Na poradí tunelov ani na poradí čísel \(a\) a \(b\) vo výstupe nezáleží. Ak je správnych odpovedí viac, vypíšte ľubovoľnú z nich.

Je zaručené, že každý vstup má platné riešenie.

Príklady

Input:

3
1 2
0 2
0 0
1 1
2 3

Output:

0 1
1 2

Máme tri kolónie. Očíslované sú \(0\), \(1\) a \(2\). Tunel má viesť medzi kolóniami \(1\) a \(2\) a medzi kolóniami 0 a 2. Tri pozície sú \([0, 0]\), \([1, 1]\) a \([2, 3]\). Príkladový výstup hovorí, že spojíme pozíciu číslo \(0\) s pozíciou \(1\) a tiež \(1\) s \(2\). To znamená, že jeden tunel bude medzi \([0, 0]\) a \([1, 1]\) a druhý medzi \([1, 1]\) a \([2, 3]\). Keby sme si to znázornili na štvorčekovú sieť súradníc, videli by sme, že sa žiadne dva tunely nepretínajú. Okrem toho je zachovaný aj spôsob prepojenia kolónií: Buď by bola kolónia číslo \(1\) v \([0, 0]\) a kolónia \(0\) v \([2, 3]\), alebo naopak.

Iné platné riešenie by mohlo spojiť pozície \(1\) s \(2\) a \(2\) s \(0\)

Input:

5
0 1
1 2
2 3
3 4
0 0
9 9
2 3
3 2
7 8

Output:

0 3
3 1
1 4
4 2

Podľa tohto výstupu by boli tunely postavené takto:

---

1. Posledné informácie hovoria o počte \(197\,359\)↩

2. Narodili sa už na Marse↩

3. Pricestovali na Mars↩

4. Keďže budú chránené v podzemí↩

5. 1373 km/h↩

6. Ani predseda Medzinárodnej rady vesmírnych agentúr nevedel zdôvodniť toto rozhodnutie↩

7. Aj keď je jasné, že Mars nie je plochý, pre účely tejto úlohy postačí, že povrch Marsu budeme považovať za rovinu a použijeme obyčajnú karteziánsku súradnícovú sústavu.↩

Keďže zadanie úlohy je pomerne dlhé, zhrňme si najprv, o čo tu ide. Na vstupe máme popísaný graf (strom) s \(n\) vrcholmi a \(n\) bodov v rovine. Úlohou je položiť vrcholy grafu do bodov v rovine tak, aby sa žiadne hrany nepretínali. Pritom hrany grafu sa zobrazia na úsečky medzi bodmi v rovine. Ako to spraviť?

Riešenie hrubou silou

Prvou možnosťou by bolo niečo veľmi pomalé. Všetkým bodom v rovine priradíme nejaké vrcholy grafu a skontrolujeme, či nám kolidujú nejaké hrany. Ak áno, skúsime vrcholy rozmiestniť nejako inak. Inak povedané, permutácie usporiadanej množiny vrcholov skúšame zobraziť na usporiadanú množinu bodov, kým nenájdeme správne riešenie.

Hmmm. Jednak by to bolo trochu neefektívne, že aj keď zmeníme medzi jednotlivými permutáciami len malú časť vrcholov, zase musíme kontrolovať všetky dvojice úsečiek, a dvak, asi nechceme skúšať všetky permutácie, chceme tento problém vyriešiť nejako rozumne postupne.

Čo keby sme vrcholy ukladali postupne po jednom a pre každý pridaný vrchol by sme hneď zistili, či sa jeho položením niečo preťalo? Tým pádom by sme vedeli, či má zmysel pokračovať v takomto rozložení vrcholov. Takto by nám stačilo vždy pri uložení vrcholu skontrolovať len tie hrany, ktorými sme tento vrchol pripojili ku zvyšku grafu.

Úlohu si vyriešime rekurzívne tak, že v každom kroku máme \(x\) vrcholov už uložených a \(n - x\), ktoré sú ešte voľné. Keďže chceme skúšať rôzne možnosti uloženia vrcholov, stačí nám meniť poradie vrcholov a body v rovine necháme napríklad v poradí zo vstupu. Preto majme usporiadanú množinu bodov v rovine. V \(i\)-tom kroku uložíme nejaký vrchol do bodu \(i\).

Na začiatku \(x = 0\). Vyberieme si nejaký vrchol, ten uložíme, skontrolujeme, či sa jeho hrany s niečím nepretínajú, a krok opakujeme s \(n - x\) vrcholmi. Ak v nejakom kroku zistíme, že ešte máme neuložené vrcholy a nevieme už žiaden uložiť tak, aby nám nič nekolidovalo, vrátime sa o krok späť a skúsime namiesto naposledy uloženého vrcholu uložiť nejaký iný a pokračovať ďalej. Toto opakujeme, až kým nie sú všetky vrcholy uložené. Všimnime si, že keď sa zasekneme a pozmeníme nejako uloženie, nemusíme zase porovnávať všetky dvojice úsečiek, ale len tie, ktoré zahrňajú novo pridané hrany.

Takýto dynamický prístup síce vyzerá pekne, no jeho asymptotická časová zložitosť až tak pekne nevyzerá. Hrozí tu, že v najhoršom prípade potrebujeme preveriť \(n!\) uložení grafu, pričom ale pre každú vetvu výpočtového stromu skontrolujeme \(n^2\) dvojíc úsečiek. Z toho nám vychádza časová zložitosť \(O(n! \cdot n^2)\).¹

Zamyslime sa. Doteraz sme pracovali s myšlienkou, že budeme nejakým spôsobom skúšať napasovať zadaný graf do zadaných súradníc a testovať pri tom, či je daná možnosť vyhovujúca alebo niečo koliduje. Čo keby sme vedeli nejakým spôsobom vopred zaručiť, že vybrané uloženie je korektné, aj bez potreby overovania?

Vzorové riešenie

Každý strom si vieme rozdeliť na menšie podstromy a tie na menšie podstromy a tak ďalej, až dostaneme strom hĺbky \(1\). Strom hĺbky \(1\) môžeme inak nazvať hviezda. Takto nízky strom vieme uložiť do roviny ľubovoľne a aj tak sa nestane, že sa nejaké hrany budú pretínať (samozrejme počítame s tým, že žiadne 3 body neležia ne jedenej priamke).

Ak si zvolíme v zadanom strome nejaký koreň, potom si predstavme podstromy, ktorých koreňmi sú jeho synovia. Každý takýto podstrom bude okupovať nejakú časť roviny, ktorú vieme ohraničiť konvexným obalom jeho vrcholov. Ak by sme vedeli tieto pre každý podstrom vybrať množinu tak, aby sa ich obaly nepretínali, mali by sme už čiastočne vyhrané. Totiž ak sa obaly nepretínajú, nemôžu sa pretínať ani hrany. Ak by sme toto vedeli opakovať rekurzívne do hĺbky, mali by sme vyhrané úplne, lebo takto vieme uložiť všetky vrcholy grafu.

Jediné, čo už teraz potrebujeme vyriešiť je, ako rozdeliť body v rovine do jednotlivých podstromov tak, aby sa ich obaly nepretínali. Keď budú body každého podstromu “pri sebe”, tak snáď nebudú zavadzať iným podstromom. Chceme ich teda “poskupinkovať” nejako lokálne.

Dobre. Z pohľadu ľubovoľného bodu koreňa vidíme každý iný bod pod nejakým uhlom. Zo zadania sme sa dočítali, že žiadne tri body neležia na rovnakej priamke. Preto vieme, že takýto uhol je pre každý bod unikátny. Hmmm. Ak sme v koreni a všetky dostupné body utriedime podľa tohto uhla, vieme si ich v tomto poradí “poskupinkovať” a prerozdeliť svojim synom. Tým pádom sa žiadna skupina bodov “nemieša” s nejakou inou, pretože body každej tejto množiny pozorujeme pod uhlom z nejakého intervalu, pričom body ďalšej sledujme pod uhlom z iného intervalu, pričom tieto intervaly majú prázdny prienik.

A funguje to vždy? Nie.

Ak si pre koreň vyberieme ľubovoľný bod, môže sa stať, že interval, pod ktorým vidíme istú množinu bodov bude väčší než \(\pi\), čo by znamenalo, že plocha ohraničená konvexným obalom tejto množiny bodov by obsahovala aj koreň. Tým pádom, by sa mohlo stať, že nejaká hrana v tomto území by pretínala hranu medzi koreňom a iným synom. Tento problém vieme ale jednoducho vyriešiť tak, že ako koreň stromu zvolíme najľavejší bod. To nám zaručí, že všetky ostatné body sa budú nachádzať vpravo od neho, čo inak znamená aj to, že interval uhlov, pod ktorými budú viditeľné z koreňa, bude najviac od \(\frac{\pi}{2}\) po \(- \frac{\pi}{2}\) otvorený z aspoň jednej strany, keďže žiadne tri body neležia na rovnakej priamke.

Ten istý problém sa môže stať aj na ďalších úrovniach: možno sa podstrom zobraznený na svojej pridelenej podmnožine pretne s hranou, ktorá je medzi jeho koreňom a jeho otcom. To opäť vyriešime extrémnou voľbou koreňa podstromu: ak ho umiestnime do prvého bodu v poradí (podľa uhla). Keďže všetky ostatné body budú zvierať s jeho otcom menší uhol, nebude tak možné, aby sa ľubovoľná úsečka medzi týmito bodmi pretla s tou spomenutou.

Tým pádom všetky usporiadané podmnožiny bodov sú pridelené nejakým podstromom. To znamená, že túto úlohu vieme vyriešiť pekne rekurzívne.

Najprv si porebujeme prehľadaním do hĺbky spočítať veľkosti jednotlivých podstromov, aby sme neskôr vedeli, koľko bodov máme konkrétnemu podstromu vyčleniť. Potom už vieme rekurzívnym prehľadávaním do hĺbky ukladať najprv koreň celého stromu, potom jeho synov a tak ďalej, pričom vždy uložíme koreň, polárne utriedime zvyšné body práve vzhľadom na koreň daného podstromu a rozdelíme tieto body jeho synom, podľa veľkostí ich podstromov.

Zložitosti. To, že vrcholy ukladáme do roviny rekurziou do hĺbky, nás môže ľahko zlákať na myšlienku, že pre každú úroveň rekurzie si potrebujeme pamätať zase novú množinu bodov, lebo si chceme pôvodnú usporiadanú množinu pamätať pre prípad, že sa k nej z rekurzie vrátime a budeme s ňou ďalej pracovať. Najhorší prípad by potom nastal, ak by graf na vstupe bol cesta a zakorenili by sme si ho ma jej konci. Vtedy by sme si najprv pamätali \(n\) bodov, potom \(n - 1\), \(n - 2\), \(\dots\) čo je asymptoticky \(n^2\). Z toho dostávame teda zložitosť \(O(n^2)\).

Uvedomme si ale, že ak časť (istý súvislý úsek usporiadanej množiny) bodov priradíme nejakému synovi a jeho podstromu, ostatní synovia s touto časťou už nepracujú. Preto nevadí, že v tejto podmnožine zmeníme poradie prvkov predtým, ako rozdelíme aj všetky ostatné prvky. To znamená, že nám úplne postačuje pamätať si množinu všetkých bodov len raz a potom pracovať s jej podmnožinami bez toho, aby sme museli zachovaávať pôvodné poradie. Pamäťovú zložitosť tohto riešenia tak vieme odhadnúť na \(O(n)\).

A časová zložitosť? Spočítanie veľkostí podstromov trvá len \(O(n)\). Triediť vieme v \(O(n \log n)\), ale potrebujeme to robiť pre každý podstrom, no na druhej strane, pre každý podstrom sa nám mení \(n\). V najhoršom prípade by zadaný graf bol cesta. Vtedy by sme vždy v \(i\)-tej úrovni rekurzie polárne triedili \(n - i\) bodov a úrovní by bolo \(n\). Z toho nám vychádza asymptotická časová zložitosť \(O(n^2 \log n)\).

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct Point {
	long x, y;
	int id;
};

// porovnavacia funkcia pre usporiadanie podla x-ovej suradnice
bool compare_x (Point a, Point b) {
	return a.x < b.x;
}

// chceme rozhodovat o poradi dvoch bodov, co zavisi od tretieho
// vieme to implementovat cez objekt toho tretieho bodu:
class CompareClass {
public:
	Point root;

	CompareClass (Point p) : root(p) {}

	// porovnavacia metoda pre polarne triedenie
	bool operator() (const Point a, const Point b) {
		return ((a.x - root.x) * (b.y - root.y) - (b.x - root.x) * (a.y - root.y)) > 0;
	}
};

vector <int> Tree_size;
vector <vector <int> > Node, Syn; 
vector <Point> Points;

void dfs (int node, int parent) {
	Tree_size[node] = 1; // 1 bod zaberie uz koren podstromu

	for (int i = 0; i < Node[node].size(); i++) {
		
		int syn = Node[node][i];
		if (Node[node][i] != parent) { // ak to nie je moj parent
			dfs(Node[node][i], node); // vypocitam velkost
			Syn[node].push_back(syn); // a dam do zoznamu synov
			Tree_size[node] += Tree_size[syn];
		}
	}
}

int solve (int node, int left, int right) {
	CompareClass compareClass(Points[left]); // koren je v prvom bode
	
	if (right - left > 1) // polarne triedenie
		sort(Points.begin() + left + 1, Points.begin() + right, compareClass);

	int tmp = 1; // 1 bod uz pre samotny koren
	for (int i = 0; i < Syn[node].size(); i++) {
		// zvysne rozdelime synom

		int left_border = left + tmp;
		tmp += Tree_size[Syn[node][i]];
		int right_border = left + tmp;

		// tunel ma existovat medzi aktualnym korenom a jeho synom
		printf("%d %d\n", compareClass.root.id, solve(Syn[node][i], left_border, right_border));
	}

	return compareClass.root.id;
}

int main(){
	int n;
	scanf("%d", &n);

	Tree_size.resize(n);
	Node.resize(n);
	Syn.resize(n);
	Points.resize(n);

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		Node[a].push_back(b);
		Node[b].push_back(a);
	}

	// spocitame velkosti podstromov
	dfs(0, -1);

	for (int i = 0; i < n; i++) {
		scanf("%ld %ld", &Points[i].x, &Points[i].y);
		Points[i].id = i;
	}

	// zoradime podla x-ovej suradnice
	sort(Points.begin(), Points.end(), compare_x);
	
	solve(0, 0, n);
}

Poznámka na záver: to, že týmto spôsobom nájdeme správne riešenie, neznamená, že nájdeme jediné správne. Môže existovať strom uložený v rovine aj keď neexistuje taký jeho koreň, z ktorého by sme videli množiny bodov podstromov jeho synov a vedeli si ich takto rozdeliť do konvexných množín. My sme chceli len nájsť ľubovoľné riešenie pre uloženie stromu, nie všetky.