Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | dreapta.in, dreapta.out | Sursă | Infoarena Monthly 2014, Runda 2 |
Autor | Andrei Cristian Lambru | Adăugată de | |
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.
Cerinta
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.
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 ori 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
- 1 ≤ Q ≤ 100 000
- 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
Exemplu
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 | 1 1 0 0 1 0 |