dreapta

Dreapta

== include(page="template/taskheader" task_id="dreapta") ==

Poveste şi cerinţă...

Se da un poligon simplu, nu neaparat convex.
 
h2. Cerinţă
 
Se dau Q intrebari de tipul: Punctul cu coordonatele x, y se afla in interiorul poligonului?

h2. Date de intrare

Fişierul de intrare $dreapta.in$ ...

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$ ...

Î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$
* $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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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
0
1

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="dreapta") ==

9656