Fișierul intrare/ieșire	elicop.in, elicop.out	Sursă	OJI 2012 clasa a 9-a
Autor	Doru Popescu Anastasiu	Adăugată de	Coman Isabela Patricia • Isabela_coman
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Elicop (clasa a 9-a)

Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrățele de aceeași dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrățele de gazon sunt numerotate de sus în jos cu numerele 1, 2, ..., m, iar coloanele cu pătrățele de gazon sunt numerotate de la stânga la dreapta cu numerele 1, 2, ..., n. Din cauza tipului diferit de iarbă se știe care dintre pătrățele de gazon sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional a cu m linii și n coloane, cu elemente 0 și 1 (aij= 0 înseamnă că pătrățelul aflat pe linia i și coloana j este afectat de umbră, iar aij= 1 înseamnă că pătrățelul aflat pe linia i și coloana j nu este afectat de umbră). Fiecare elicopter are 3 roți pe care se sprijină. Roțile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere.

Pentru a preciza poziția unui elicopter pe teren este suficient să cunoaștem linia și coloana vărfurilor ipotenuzei și poziția vârfului deasupra (codificată prin 1) sau dedesubtul ipotenuzei (codificată prin -1). Pentru exemplu, elicopterul din stânga sus este dat prin (1,1), (3,3) și -1, cel din dreapta sus prin (1,9), (5,5) și 1, cel din stânga jos prin (5,1), (6,2) și 1, iar cel din dreapta jos prin (5,9), (6,8) și 1.
Un elicopter se consideră că a aterizat greșit, dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrățele afectate de umbră.
Administratorul terenului de fotbal dorește să determine numărul N1 de elicoptere, care nu afectează nici un pătrățel din teren și numerele de ordine al elicopterelor, care au aterizat greșit în ordine crescătoare: e1, e2, ..., eN2, știind că există k elicoptere codificate prin numerele 1, 2, ..., k.

Cerință

Scrieți un program care să determine, pentru fișierul cu datele din enunț: numărul de elicoptere N1, care nu afectează nici un pătrățel din teren și numerele de ordine al elicopterelor, care au aterizat greșit în ordine crescătoare, precedate de numărul lor N2.

Date de intrare

Prima linie a fișierului de intrare elicop.in conține două numere naturale m și n, separate printr-un spațiu, cu semnificația din enunț. Următoarele m linii conțin câte n numere 0 sau 1, separate prin câte un spațiu cu semnificația 0 – pătrățel de gazon care este afectat de umbră, respectiv 1- pătrățel care nu este afectat de umbră. Pe linia m+2 se află numărul de elicoptere k, iar pe următoarele k linii (în ordinea codificării lor 1, 2, ..., k) câte cinci numere separate prin cate un spațiu, pentru liniile și coloanele ipotenuzelor și poziția vârfului (1 sau -1), triunghiurilor dreptunghice asociate elicopterelor:
L1 C1 L2 C2 p.

Date de ieșire

Fișierul de ieșire elicop.out va conține două linii: prima linie numărul N1 de elicoptere, pe care nu afectează nici un pătrățel din teren, a doua linie cu numerele naturale N2, e1, e2, ..., eN2 separate prin câte un spațiu, în ordine crescătoare.

Restricții

• ... ≤ ... ≤ ...
• 2 ≤ m, n ≤ 100
• 1 ≤ k ≤ 40
• Nu există suprapuneri de triunghiuri asociate la două elicoptere.
• Triunghiurile asociate elicopterelor conțin cel puțin trei pătrățele.

Exemplu