În satul Şeseni fiecare familie are un lot de pământ de forma unui poligon convex, iar serviciul de cadastru din sat cunoaşte coordonatele întregi ale fiecărui punct care delimitează laturile poligoanelor, raportate la un sistem de axe rectangulare cu originea în centrul satului. Un exemplu pentru 4 loturi este dat în imaginea alăturată.


Într-o zi de vară a început să plouă, iar apoi ploaia s-a transformat în grindină ″cât oul de porumbel″. Grindina a căzut în mod inegal peste loturile oamenilor astfel încât recolta a fost mai mult sau mai puţin compromisă. Staţia meteo din sat a reuşit (minune!) să numere câtă grindină a căzut, ba, mai mult, unde anume a căzut fiecare bob de grindină.

Cerinţă

Determinaţi lotul/loturile de teren pe care a căzut cea mai mare cantitate de grindină precum şi lotul/loturile neafectate de grindină.

Date de intrare

Fişierul de intrare grindina.in conţine pe prima linie numărul nrl de loturi. Următoarele nrl linii conţin fiecare descrierea unui lot şi au următoarea structură:
nrp x1 y1 x2 y2 ... xnrp ynrp
unde nrp este numărul de puncte ale poligonului convex care descrie lotul, iar xi yi sunt coordonatele întregi ale celor nrp puncte, date în sens trigonometric. Valorile sunt separate prin câte un spaţiu.
Următoarea linie a fişierului de intrare conţine o valoare naturală G, reprezentând numărul de boabe de grindină căzute. Ultimele G linii conţin fiecare câte două numere întregi xg yg, separate printr-un spaţiu, reprezentând coordonatele locului unde a căzut bobul de grindină corespunzator.

Date de ieşire

Fişierul de ieşire grindina.out conţine pe prima linie o valoare care reprezintă numărul de loturi pe care a căzut cea mai mare cantitate de grindină. Linia a doua conţine numerele de ordine ale loturilor respective ordonate crescător. Pe linia a treia se găseşte un număr natural care reprezintă numărul de loturi neafectate, iar pe linia a patra numerele de ordine ale acestora, în ordine crescătoare. Loturile sunt numerotate de la 1, în ordinea în care sunt specificate în fişierul de intrare.

Restricţii

• 0 < nrl <= 100
• 0 <= G <= 1000
• Grindina căzută pe marginile lotului nu afectează cultura.
• Pot exista configuraţii de loturi ca în figura alăturată.


• Numărul de laturi ale unui lot este maxim 5.

Exemple

grindina.in	grindina.out	Explicaţii
4 3 0 0 -1 4 -3 -4 4 0 0 4 -2 7 4 -1 4 5 0 0 -3 -4 -1 -9 3 -9 4 -2 4 4 -2 3 -9 6 -5 7 4 14 1 1 2 2 3 3 2 5 0 -1 -1 -1 -1 -3 -2 -5 1 -3 2 -4 3 -8 5 -3 6 -4 6 0	1 3 0 0	Exemplul este cel din prima imagine: Deci coeficientul minim este la lotul 2. Obs. Bobul de grindină de coordonate (2,5) nu a căzut pe nici un lot.

autor: Prof. Marinel Şerban

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com