Kreslení binárního stromu

Binární strom chceme vizualizovat na čtvercové mřížce, která má tvar obdélníku. Předpokládáme, že levý dolní roh uvažované mřížky má souřadnice (0,0), vzdálenost mezi sousedními mřížovými body je jednotková a souřadnice rostou směrem vpravo a nahoru. Pravidla pro nakreslení stromu jsou následující:

  1. Každý uzel binárního stromu reprezentujeme kružnicí se středem v některém mřížovém bodě čtvercové mřížky. Poloměr kružnice je menší než 0,5. Kružnice reprezentující uzly stromu, které jsou ve vztahu rodič a potomek, jsou následně spojené úsečkou.
  2. Nechť u1 a u2 jsou uzly stromu reprezentované kružnicemi, jejichž středy mají souřadnice (x1,y1) a (x2,y2).
    • Mají-li u1 a u2 stejnou hloubku, pak y1=y2. Má-li u1 větší hloubku než u2, potom y1<y2.
    • Je-li u1 v levém podstromu uzlu u2, potom x1<x2. Naopak, je-li u1 v pravém podstromu uzlu u2, potom x1>x2.
  3. Použitá čtvercová mřížka má nejmeší možnou plochu.

     


Obrázek 1. Příklady vizualizací binárních stromů ve čtvercové mřížce. Rozměry mřížek jsou a) 3×4, b) 4×6, c) 4×10.

Úloha

Pro daný binární strom určete souřadnice středů kružnic, které reprezentují jeho uzly v definovaném nakreslení stromu.

Vstup

První řádek obsahuje tři celá nezáporná čísla N, R, L oddělená mezerou představující po řadě počet uzlů binárního stromu, identifikátor kořene a délku seznamu vybraných uzlů, pro které jsou na výstupu požadovány souřadnice středů reprezentujících kružnic. Následuje N−1 řádků vstupu reprezentujících postupně všechny hrany stromu. Každý řádek obsahuje dvě nezáporné hodnoty U, V oddělené mezerou. Tyto hodnoty představují identifikátory uzlů spojených hranou. Uzly jsou číslovány 0, ..., N−1. Pořadí hran je v zásadě libovolné, stejně tak je i libovolné pořadí koncových uzlů hrany (není tedy zřejmé, zda je U rodičem V, či naopak). Platí ale pravidlo, že pro každý uzel, který má dva potomky, se v seznamu hran vyskytne nejdříve hrana, která uzel spojuje s jeho levým potomkem. Znamená to mimo jiné, že pokud uzel má pouze jednoho potomka, jedná se vždy o levého potomka. Poslední součástí vstupu je L řádků, kde každý řádek obsahuje jeden identifikátor uzlu.

Hodnota N je větší než 1 a nepřesáhne 1,6 × 106, pro hodnotu L platí 1 ≤ L ≤ 100, navíc také L ≤ N.

Výstup

Výstupem je L řádků. Označíme-li u1, ..., uL vstupní seznam vybraných uzlů délky L, potom pro každé i=1,2, ..., L obsahuje i-tý výstupní řádek x-ovou a y-ovou souřadnici středu kružnice reprezentující uzel ui. Souřadnice jsou na řádku od sebe oddělené mezerou.

Příklad 1

Vstup
4 0 2
0 1
0 3
2 3
0
3

Výstup
1 2
3 1
Nakreslení stromu z příkladu 1 je znázorněno na obrázku 1a).

Příklad 2

Vstup
6 1 4
3 4
3 0
4 5
1 3
2 4
5
2
1
4

Výstup
0 0
2 0
5 3
1 1
Nakreslení stromu z příkladu 2 je znázorněno na obrázku 1b).

Příklad 3

Vstup
10 5 3
2 4
4 1
0 6
7 6
8 9
4 5
6 3
3 5
3 8
1
3
9

Výstup
2 1
7 2
8 0
Nakreslení stromu z příkladu 3 je znázorněno na obrázku 1c).

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data