Fișierul intrare/ieșire | tangente.in, tangente.out | Sursă | ad-hoc |
---|---|---|---|
Autor | clasică | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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 |