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.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.