6. Yyha to je šuter

Bubu sa jedného dňa prechádzal po lese, keď mu do oka padol šuter. Chvalabohu, iba metaforicky, nie doslova. Šutrák to bol riadny, čo Bubua potešilo, až radostne zýýkol (Yyyyyy!). No keď si Bubu uvedomil, že má tento balvan v ceste, radosť ho prešla. Pobral sa ho obísť, no hneď za šutrom, na čistine, mu jeden strom, starý hodne, zahatil, aby nezaspal, preventívne cestu tým, že sa vyvalil. Bubu sa nenechal odradiť a aj túto prekážku obišiel. Potom, čo obišiel tento strom, sa mu kdesi v podlesí zjavili v ceste dva vresy (a to riadne prerastené). Za mohutným sudom od kapusty (ktorý musel tiež chudák obchádzať) ležali vyvalené 4 bresty. A tak ďalej, (no viete si to domyslieť), no a keď bol koniec prechádzky, tak mu do cesty vošli sanitky.

Tak s potom až na brade, vo vysilenej nálade, Bubu dokončil svoje trápenie počnuté kusom žuly. Teraz hľadá optimálne riešenie ako obísť skaly.

Úloha

Vašou úlohou je nájsť najkratšiu trasu z pozície udanej začiatočnými koordinátmi na pozíciu udanú konečnými koordinátmi, ktorá neprechádza žiadnou z popísaných prekážok. Prekážky sú buď úsečkami, alebo konvexnými mnohouholníkami.

Vo všeobecnosti platí, že sa tieto prekážky nedotýkajú. Inak povedané, začiatok a koniec žiadnej úsečky, vrátane vrcholov mnohouholníkov, nikdy neležia uprostred inej úsečky. (V niektorých sadách sa ale úsečky môžu pretínať a zdieľať koniec/začiatok)

Pozn.: Cesta môže prechádzať pozdĺž prekážky, aj cez jej začiatok a koniec, ale nie cez samotnú prekážku, čo v prípade mnohouholníkov znamená, že môže ísť po obvode ale nie cez ich vnútro.

Formát vstupu

Na prvom riadku vstupu sú štyri čísla \(x_s,\) \(y_s,\) \(x_e,\) \(y_e\) popisujúce koordináty začiatku (\(x_s,\) \(y_s\)) a konca (\(x_e,\) \(y_e\)) trasy, ktorú chce Bubu prejsť.

Druhý riadok obsahuje jedno číslo \(n\), počet prekážok.

Nasleduje \(2n\) riadkov, ktoré po pároch popisujú prekážky na trase. Riadok číslo \(2k\) obsahuje jedno číslo \(m_k\geq 2\), počet bodov popisujúcich \(k\)-tú prekážku. V prípade, že \(m_k=2\), je prekážka úsečkou, v opačnom prípade je mnohouholníkom.

Riadok číslo \(2k+1\) obsahuje \(2m_k\) čísel vo formáte \(x_0,\) \(y_0,\) \(\dots\) \(x_{m_k-1},\) \(y_{m_k-1}\), ktoré popisujú koordináty prekážky, v poradí.

V jednotlivých sadách platia nasledujúce obmedzenia:

V sadách 1, 2, 3, 4 môžete predpokladať, že sa žiadne dve úsečky nepretínajú. V sadách 1, 3, 5, 7 navyše platí \(m_i=2\), vo všeobecnosti platí \(m_i\leq10\).

Formát výstupu

Vypíšte dĺžku najkratšej možnej trasy zo začiatku na koniec. Váš výsledok by mal byť najviac \(10^{-6}\) rozdielny od očakávaného výsledku.

Príklady

Input:

0.0 0.0 4.0 0.0 
3
2
1.0 -1.0 1.0 1.0
2
2.0 4.0 2.0 0.0
2
3.0 1.0 3.0 -4.0

Output:

5.656854249492381

Prekážky sú čierne úsečky s vyznačeným koncom a začiatkom, optimálna trasa je červenou.

Input:

0.0 0.0 4.0 0.0 
4
2
1.0 -1.0 1.0 1.0
2
2.0 4.0 2.0 0.0
2
2.0 0.0 2.0 -4.0
2
3.0 1.0 3.0 -1.0

Output:

5.656854249492381

V prípade, že dve úsečky zdieľajú jeden koniec, môže tade prechádzať trasa.

Input:

0.0 0.0 6.0 0.0
1
4
2.0 2.0 2.0 -2.0 4.0 -2.0 4.0 2.0

Output:

7.656854249492381

Podobne ako vyššie, štvorcová prekážka je hnedou.