Prințesa

Prințesa Ale a fost capturată de Împărăteasa Khan ca să îi folosească părul pentru o poțiune magică. Împărăteasa o întemnițează pe Ale într-o închisoare specială. Din fericire, Claudiu Codreanu, prietenul cel mai bun al Prințesei, vrea să o ajute să scape!

Prințesa Ale, ca toate prințesele, are formă de poligon (nu neapărat convex), cu $N$ laturi. Închisoarea Împărătesei are tot formă de poligon, având $N$ pereți care îi înfășoară perfect laturile prințesei de jur împrejur. Să presupunem că cei $N$ pereți se suprapun perfect pe laturile lui Ale, iar Claudiu Codreanu vrea să demonstreze că o poate elibera pe prințesă cu un minim de efort. El propune că prințesa poate să se elibereze singură prin distrugerea unui singur perete al închisorii și voi sunteți cei care trebuie să-i dați un reality check și să spuneți dacă asta chiar este posibil sau nu. După distrugerea unui perete, prințesa se va elibera printr-o succesiune de mișcări de translație și rotație. (Formal, scopul este să ajungă la o distanță arbitrar de mare de pereții rămași).

Detalii de implementare

Va trebui să implementezi funcția

bool can_escape(std::vector<int> x, std::vector<int> y);

Poligonul are $N$ puncte date în ordine trigonometrică (inversă acelor de ceasornic): $(x[0], y[0])$, $(x[1], y[1])$, $\ldots,$ $(x[N - 1], y[N - 1])$. Funcția returnează o singură valoare booleană: true dacă răspunsul este Da și false altfel.

Comisia poate apela funcția de mai multe ori în cadrul aceluiași test.

Restricții și precizări

• $3 \leq N \leq 1 \ 000 \ 000$.
• $\text{x.size()} = \text{y.size()} = N$
• Fie $S$ suma valorilor $N$ pentru toate apelurile funcției din test.
• $S \leq 10 \ 000 \ 000$
• Poligonul nu se auto-intersectează, nu se auto-atinge și nu are vârfuri consecutive coliniare.
• Valoarea absolută maximă a coordonatelor este $1 \ 000 \ 000 \ 000$.

Exemplul 1

input

1
7
3 12
6 2
9 8
12 -2
18 6
21 2
23 12

output

Test 1: 1

Explicație

Vezi desenul din enunț.