Fişierul intrare/ieşire:tangente.in, tangente.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie1024 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Tangente

Se dă un poligon convex cu N vârfuri de coordonate reale, P1(x1, y1), P2(x2, y2), ..., Pn(xn, yn). Se mai dau K interogări, fiecare interogare constând dintr-un punct Q(x, y) situat în afara poligonului. Să se răspundă la fiecare interogare printr-o pereche de numere întregi (i, j) unde

  • i < j
  • Dreptele QPi şi QPj sunt tangente la poligon. O dreaptă este tangentă la poligon dacă îl intersectează într-un singur punct.

Date de intrare

Fişierul de intrare tangente.in conţine pe prima linie valorile N şi K. Pe următoarele N linii se află câte o pereche de numere xi yi reprezentând coordonatele vârfurilor poligonului, în ordine inversă acelor de ceasornic. Pe următoarele K linii se află câte o pereche de numere x y, reprezentând coordonatele unei interogări.

Date de ieşire

În fişierul de ieşire tangente.out se vor tipări K linii. Fiecare linie va conţine o pereche de numere întregi i j reprezentând răspunsurile la interogări. Ordinea răspunsurilor va coincide cu ordinea întrebărilor.

Restricţii

  • 3 ≤ N ≤ 10.000
  • 1 ≤ K ≤ 10.000
  • Coordonatele punctelor sunt numere cu maxim 5 zecimale din intervalul [-1.000.000, 1.000.000].
  • Interogările Q nu se află în prelungirea nici unei laturi a poligonului.

Exemplu

tangente.intangente.out
5 2
2 1
5 2
4 7
1.00000 6.00000
1 3
4 -1
0 7
1 2
3 5

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici