Se da un poligon simplu, nu neaparat convex.
h2. Cerinta
h2. Cerinţă
Se dau Q intrebari de tipul: Punctul cu coordonatele x, y se afla in interiorul poligonului?
h2. Date de intrare
Pe prima linie a fisierului de intrare $dreapta.in$ se va afla valoarea $N$ reprezentand numarul de varfuri ale poligonului. Pe urmatoarele N linii se vor afla cate doua valori reale semnificand coordonatele varfurilor poligonului. Se garanteaza ca oricare doua puncte adiacente definesc o latura a poligonului.
Pe prima linie a fisierului de intrare $dreapta.in$ se va afla valoarea $N$ reprezentand numarul de varfuri ale poligonului. Pe urmatoarele N linii se vor afla cate doua valori reale semnificand coordonatele varfurilor poligonului. Se garanteaza ca oricare doua puncte adiacente definesc o latura a poligonului. De asemenea dreapta care uneste primul si ultimul punct este o latura a poligonului.
Pe urmatoarea linie se va afla numarul natural $Q$ semnificand numarul de query-uri. Pe urmatoarele $Q$ linii se vor afla cate doua valori reale semnificand coordonatele punctelor din query-ul respectiv.
h2. Date de ieşire
În fişierul de ieşire $dreapta.out$ se vor afla $Q$ linii. Linia cu indicele $i$ va avea ori valoarea $1$ daca punctul cu indicele $i$ din query-uri se afla in interiorul poligonlui, sau valoarea $0$ altfel.
În fişierul de ieşire $dreapta.out$ se vor afla $Q$ linii. Linia cu indicele $i$ va avea valoarea $1$ daca punctul cu indicele $i$ din query-uri se afla in interiorul poligonlui sau valoarea $0$ altfel.
h2. Restricţii
* $1$ ≤ $N$ ≤ $100 000$
* $1$ ≤ $Q$ ≤ $100 000$
* $2$ ≤ $Q$ ≤ $100 000$
* $-10^9^$ ≤ $x$, $y$ ≤ $10^9^$, pentru toate coordonatele punctelor din input
* *Se garanteaza ca toate punctele din query-uri se vor afla pe aceeasi dreapta*
* Pentru a evita erorile de precizie sau cazurile particulare se garanteaza urmatoarele:
** Dreapta pe care se afla query-urile nu va intersecta niciun varf al poligonului
** Nicio latura a poligonului nu va fi paralela cu axa Oy
** Niciun punct din query-uri nu se va afla pe o latura a poligonului
** Dreapta pe care se afla query-urile nu este paralela cu axa Oy
h2. Exemplu
table(example). |_. dreapta.in |_. dreapta.out |
| 10
5 6
3 5
1 4
2 1
3 1
4 4
5 1
8 4
11 2
9 5
6
3 3
6 3
9 3
10 3
11 3
22 3
| 5
3.0 1.0
1.0 4.0
3.0 5.0
5.0 5.0
4.0 2.0
3
3.0 4.0
5.0 6.0
3.5 4.5
| 1
1
0
0
1
0
|
== include(page="template/taskfooter" task_id="dreapta") ==
