Cerința
Demult într-o vreme îndepărtată trăiau Foarte mulți porci. Pentru că erau atât de mulți trebuia să le fie construite anumite țarcuri reprezentate prin poligoane nu neapărat convexe. Din cauza unui antrenament militar cu focuri de armă mai mulți porci riscau să moară.
Se dau N
poligoane nu nepărat convexe reprezentând țarcurile porcilor, toate complet în cadranul 1
. Fiecare poligon are un cost atașat reprezentând numărul de porci din acel țarc. Se mai dă K
și K
perechi de coordonate i
-a tragere traiectoria glonțului fi o semidreaptă care va porni din (0, 0)
și va face un drum infinit de mare care va trece și prin
Date de intrare
Se va citi de la consolă N
, pe fiecare dintre următoarele rânduri se va găsi un număr i
are i
-elea țarc, apoi se va citi K
iar apoi cele K
perechi de numere descrise în enunț.
Date de ieșire
Veți afișa K
numere în consolă, toate pe o linie, al i
-elea număr reprezentând numărul de porci care ar muri dacă s-ar face doar tragerea i
.
Restricții și precizări
. . , pot fi număr negativ de porci :)).- Dacă cele
vârfuri citite pentru un poligon sunt , atunci va fi un segment de dreaptă între punctele , , …, . - Fie
cea mai mare coordonatăx
dintre toate poligoanele sau dintr-o tragere. - Fie
cea mai mare coordonatăy
dintre toate poligoanele sau dintr-o tragere.
Exemplu:
Intrare
5 3 1 3 1 2 2 2 2 4 1 1 2 1 3 2 2 3 15 4 4 1 4 2 5 2 6 2 20 5 7 1 8 1 9 1 11 1 8 2 -12 4 2 4 4 3 7 3 6 5 3 2 6 2 6 6
Iesire
20 20
Explicație
Imaginea exemplului este:
Se observă că primul poligon este roșu, al doilea portocaliu, ar treilea verde, al patrulea mov și ultimul albastru. Poligonul albastru nu este convex. La prima tragere se nimerește doar poligonul verde, la a doua tragere se nimerește poligonul roșu, portocaliu și albastru.