Fișierul intrare/ieșire tangente.in, tangente.out Sursă ad-hoc
Autor clasică Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.2 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in tangente.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii