Bunelul lui Danut este prisacar. In fiecare primavara el inchiriaza un lot, pe care plaseaza prisaca sa. Deoarece bunelului ii place sa calatoreasca, lotul este ales in fiecare primavara in alta regiune a tarii. Albinele, fiind inteligente, se deplaseaza doar in interiorul lotului inchiriat, fara a trece frontiera, care este determinata de o linie franta inchisa. Pentru a optimiza colectarea polenului, albinele trebuie sa zboare din orice punct al lotului spre stup dupa o traiectorie liniara (fara a schimba directia de zbor). Astfel, se cere respectarea urmatoarelor criterii in procesul de selectare a ofertelor cu loturi de inchiriat:

Cerinta

Ofertele primite de bunel contin descrierile mai multor loturi (vezi figura precedenta). Scrieti un program care l-ar ajuta pe Danut sa selecteze loturile care corespund criteriilor formulate in enunt.

Date de intrare

Prima linie a fisierului lot.in contine un numar natural N – numarul de loturi descrise in fisier. Descrierea fiecarui lot incepe cu o linie pe care se afla un numar natural K_i – numarul de segmente ale frontierei lotului i. Urmeaza, in ordine, descrierile varfurilor frontierei lotului, cate un varf pe linie. Descrierea varfului e data de coordonatele sale (x, y) separate prin spatiu. Descrierea lotului i se sfarseste cu o linie ce contine numerele 0 0.

Date de iesire

Fisierul lot.out va contine N linii. Linia i va contine cifra 1 daca lotul i satisface cerintele din enunt sau 0 – in caz contrar.

Restrictii

0 < N <= 20
3 <= K_i <= 1000, i= 1, ..., N
-10000 <= x, y <= 10000
x, y <> 0

Exemplu

prof. Sergiu Corlat
Liceul Moldo-turc Chisinau
Contact:scorlat@gmail.com