| Fişierul intrare/ieşire: | dreapta.in, dreapta.out | Sursă | Infoarena Monthly 2014, Runda 2 |
| Autor | Andrei Cristian Lambru | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dreapta
Se da un poligon simplu, nu neaparat convex.
Cerinţă
Se dau Q intrebari de tipul: Punctul cu coordonatele x, y se afla in interiorul poligonului?
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. 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.
Date de ieşire
Î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.
Restricţii
- 1 ≤ N ≤ 100 000
- 2 ≤ Q ≤ 100 000
- -109 ≤ x, y ≤ 109, 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
Exemplu
| dreapta.in | dreapta.out |
|---|---|
| 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 |
