3. Tesná medzera v stene vzorové riešenie

Zadanie

Pytón Peťko (možno ste sa s nim stretli, keď ste riešili seminár PRASK) mal dosť nepríjemný deň. Nejaký záškodník mu do jeho obľúbenej ovsenej kaše, ktorú si dáva každé ráno, primiešal cement. Chudák Pytón je teraz plný stvrdnutého cementu a nedokáže sa ohýbať.

Ako sa teraz dostane domov?

Úloha

Pytóna Peťka si môžeme predstaviť ako lomenú čiaru v 2D. Celou čiarou môžeme hýbať aj ju otáčať (v 2D), ale nemôžeme meniť jej tvar.

Celý pytón je na jednej strany veľkej steny (priamky) a pytónove obydlie je na druhej strane steny. V stene je tenučká štrbina. Pre jednoduchosť si predstavme, že pytón je nekonečne tenký a štrbina je nekonečne úzka.

Zistite, či sa dokáže pytón prepchať cez štrbinu v stene a dostať sa domov.

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) (\(1\leq n \leq 1\,000\)) udávajúce počet vrcholov lomenej čiary. Nasleduje \(n\) riadkov a na \(i\)-tom z nich sú dve čísla \(x_i\), \(y_i\) \((0\leq x_0\leq 10^9, 1\leq y_0\leq 10^9)\) udávajúce pozíciu \(i\)-teho vrchola lomenej čiary. Lomená čiara je teda zložená z úsečiek \((x_i,y_i)\) – \((x_{i+1},y_{i+1})\) pre \(i \in \{1..n-1\}\).

Môžete predpokladať, že lomená čiara sama seba nepretína a tiež žiadne tri vrcholy lomenej čiary neležia na jednej priamke.

Formát výstupu

Vypíšte “Possible” pokiaľ lomená čiara môže prejsť na druhú stranu steny (ktorou je priamka \(y=0\)), cez ľubovoľne malú štrbinu v bode \((0, 0)\). V opačnom prípade vypíšte “Impossible”.

Príklady

Input:

4
0 1
1 1
1 2
2 2

Output:

Possible

Input:

11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 141
19 124
0 156
22 183

Output:

Impossible

Na obrázkoch môžeme vidieť nákresy ukážkových vstupov.

V prvom rade treba vymyslieť nutnú a postačujúcu podmienku, kedy sa had dokáže prepchať cez škáru.

Had sa dokáže prepchať cez škáru práve vtedy, keď pre každý bod hada existuje priamka, ktorá prechádza týmto bodom a hada nikde inde nepretína. Zamyslite sa prečo. Všimnite si tiež, že vďaka nekolinearite každej trojice bodov nemusíme rozlišovať prípady “pretína” a “dotýka”.

Had sa dokáže prepchať cez škáru práve vtedy, keď sa pri ľubovoľnom rozseknutí hada v nejakom jeho bode na dve časti konvexné obaly týchto častí neprekrývajú (ich prienik má nulový obsah, resp. majú spoločný len jeden bod alebo úsečku). Zamyslite sa, ako toto vyplýva z predošlého pozorovania. Túto podmienku stále nevieme algoritmicky overovať, pretože možných rozseknutí je nekonečne veľa. Preto treba pokračovať v úvahách.

Had sa dokáže prepchať cez škáru práve vtedy, keď sa pri ľubovoľnom rozseknutí hada v nejakom jeho vrchole (to sú body, kde sa láme jeho telo) konvexné obaly častí neprekrývajú. Môžeme si uvedomiť, že aj prvú podmienku (s priamkami) stačí overovať len pre vrcholy hada.

Ponúka sa teda myšlienkovo jednoduché, ale implementačne náročné riešenie úlohy. Postupne vyskúšame rozseknúť hada v každom z \(n\) vrcholov, pri každom rozseknutí spočítame konvexný obal predku (všetko po bod rozseknutia vrátane) a zadku (všetko od bodu rozseknutia vrátane) hada a spočítame, či sa konvexné obaly prekrývajú. Riešenie by malo zložitosť \(O(n^2 \log(n))\).

Úloha sa dá naprogramovať aj oveľa príjemnejšie, pretože v skutočnosti nemusíme konštruovať konvexné obaly, ale stačí pre každý bod rozseknutia \(A\) spočítať interval uhlov, pod ktorými vidíme predok hada z \(A\) a zadok hada z \(A\). Ak sa intervaly prekrývajú alebo ak je niektorý interval väčší ako 180 stupňov, had sa neprepchá cez stenu.

Samozrejme, nebudeme počítať uhly, ale iba nájdeme najľavejší a najpravejší bod predku/zadku hada pomocou vektorového súčinu, vďaka čomu všetky výpočty ostanú v celých číslach. Tak sa dá úloha vyriešiť elegantne na pár riadkov, v čase \(O(n^2)\). Odporúčame premyslieť si implementáciu pred tým, ako začnete programovať.