== include(page="template/taskheader" task_id="tangente") ==
Poveste și cerință...
Se dă un poligon convex cu $N$ vârfuri de coordonate reale, $P[~1~](x[~1~], y[~1~]), P[~2~](x[~2~], y[~2~]), ..., P[~n~](x[~n~], y[~n~])$. 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 $QP[~i~]$ și $QP[~j~]$ sunt tangente la poligon. O dreaptă este tangentă la poligon dacă îl intersectează într-un singur punct.
h2. Date de intrare
Fișierul de intrare $tangente.in$ ...
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 $x[~i~] y[~i~]$ 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.
h2. Date de ieșire
În fișierul de ieșire $tangente.out$ ...
Î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.
h2. 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.
h2. Exemplu
table(example).
|_. tangente.in |_. tangente.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 2
2 1
5 2
4 7
1.00000 6.00000
1 3
4 -1
0 7
| 1 2
3 5
|
h3. Explicație
...
!problema/tangente?tangente.png!
== include(page="template/taskfooter" task_id="tangente") ==
