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ță
h2. 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.
h2. Date de intrare
Fișierul de intrare $elicop.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $elicop.out$ ...
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.
h2. 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.
h2. Exemplu
table(example).
|_. elicop.in |_. elicop.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|_. elicop.in |_. elicop.out |_. Explicație |
| 7 9
1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0
0 0 1 0 1 1 1 0 0
1 1 1 0 1 1 0 1 1
0 0 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 0 1
4
1 1 3 3 -1
1 9 5 5 1
5 1 6 2 1
5 9 6 8 1
| 2
2 1 3
| Elicopterele 2 și 4 nu afectează niciun pătrățel de gazon.
Elicopterele 1 și 3 afectează fiecare mai mult de jumătate din numărul
pătrățelelor asociate triunghiurilor dreptunghice și deci aterizează greșit.
Elicopterul 1 face umbră la 6 pătrățele, din care afectate sunt 4.
Elicopterul 3 face umbră la 3 pătrățele, din care afectate sunt două.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="elicop") ==
