Rate

Rate

În jurul unui râu se gasesc m lacuri (codificate prin 1, 2,..., m) care nu comunica între ele si nici cu râul. Marginile fiecarui lac sunt de forma poligonala (convexe sau concave). În zona lacurilor se gasesc N rate salbatice (unele pe lac, altele pe mal). Ratele sunt codificate prin 1, 2, …, N. Un grup de vânatori doresc sa vâneze rate, care plutesc pe apa. Pentru acest lucru ei aleg pentru vânatoare lacul (lacurile, daca sunt mai multe) cu suprafata cea mai mare. În aceste conditii ratele de pe acest lac (sau de pe aceste lacuri, daca sunt mai multe) sunt în pericol de a fi vânate.

Cerinta

Determinati ratele care sunt în pericol de a fi vânate.

Date de intrare

Fisierul de intrare rate.in contine:

rate.in	Semnificatie
N a₁ b₁ a₂ b₂ ... a_N b_N m c1 x₁₁ y₁₁ x₁₂ y₁₂...x_1c1 y_1c1 c2 x₂₁ y₂₁ x₂₂ y₂₂...x_2c1 y_2c1 ... cm x_m1 y_m1 x_m2 y_m2...x_mc1 y_mc1	N - numarul de rate a_i b_i -abscisa si ordonata punctului în care se gaseste rata i m - numarul de lacuri c_i reprezinta numarul de colturi ale lacului i, iar x_ij y_ijreprezinta abscisa, respectiv ordonata unui colt al lacului i. Colturile unui lac sunt date într-o ordine astfel încât sa se poata parcurge continuu malul lui.

Date de iesire

Fisierul de iesire rate.out contine pe prima linie codurile asociate ratelor care sunt în pericol de a fi vânate în ordine crescatoare (separate prin câte un spatiu). Daca nu exista rate în pericol de a fi vânate se va scrie cifra 0.

Restrictii

N numar natural, 1<=N<=50;

0<=a_i,b_i_<=100, numere reale cu maxim 4 cifre zecimale;

m numar natural, 1<=m<= 20;

c_i numere naturale, 1<=c_i<=20;

x_ij, y_ij sunt numere naturale <=100

Observatii

Malul (frontiera) unui lac nu face parte din lac;

Doua numere reale x si y le consideram egale daca |x-y|<10^-4.

Exemplu

rate.in	rate.out
4 3 5 10 4 7 1 3.002 6 2 4 9 3 11 3 11 5 9 5 5 5 3 4 5 5 7 3 7 2 5	1 4

Timp maxim de executie: 0.5 secunde/test

Prof. Doru Popescu Anastasiu

Colegiul National "Radu Greceanu", Slatina