Fişierul intrare/ieşire:dreapta.in, dreapta.outSursăInfoarena Monthly 2014, Runda 2
AutorAndrei Cristian LambruAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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

  • 1N100 000
  • 2Q100 000
  • -109x, y109, 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.indreapta.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content