== include(page="template/taskheader" task_id="rezervatie") ==
Pentru protejarea faunei şi florei salbatice, in munţii Rodnei, s-a constituit rezervaţia naturala Piatra Rea. Rezervaţia se reprezinta pe harta ca un tablou cu L linii şi C coloane. Tabloul este constituit din L*C celule patrate de latură 1. Printre plantele protejate de lege, sunt si N copaci care au fost declarati monumente ale naturii, numerotati de la 1 la N. Fiecare copac este poziţionat in centrul unei celule. Nu exista doi copaci care ocupă aceeasi pozitie. In vederea limitarii accesului în rezervatie, s-a propus construirea unei imprejmuiri, formata din segmente identice, cu lungimea egala cu cea a laturii unei celule. Segmentele sunt plasate pe conturul celulelor. Constructia imprejmuirii incepe din coltul stanga-sus al primei celule a tabloului, situata pe linia 1 şi coloana 1, si se termină in acelasi punct. Nu exista alte puncte de intersectie.
Pentru protejarea faunei si florei salbatice, in muntii Rodnei, s-a constituit rezervatia naturala Piatra Rea. Rezervatia se reprezinta pe harta ca un tablou cu $L$ linii si $C$ coloane. Tabloul este constituit din $L*C$ celule patrate de latura $1$. Printre plantele protejate de lege, sunt si $N$ copaci care au fost declarati monumente ale naturii, numerotati de la $1$ la $N$. Fiecare copac este pozitionat in centrul unei celule. Nu exista doi copaci care ocupa aceeasi pozitie. In vederea limitarii accesului in rezervatie, s-a propus construirea unei imprejmuiri, formata din segmente identice, cu lungimea egala cu cea a laturii unei celule. Segmentele sunt plasate pe conturul celulelor. Constructia imprejmuirii incepe din coltul stanga-sus al primei celule a tabloului, situata pe linia $1$ si coloana $1$, si se termina in acelasi punct. Nu exista alte puncte de intersectie.
h2. Cerinţă
Cunoscand pozitiile tuturor segmentelor imprejmuirii, dimensiunea rezervatiei si pozitiile celor N copaci monumente ale naturii, sa se identifice copacii care se gasesc in interiorul suprafetei imprejmuite.
!problema/rezervatie?figuri.jpg!
h2. Cerinta
Cunoscand pozitiile tuturor segmentelor imprejmuirii, dimensiunea rezervatiei si pozitiile celor $N$ copaci monumente ale naturii, sa se identifice copacii care se gasesc in interiorul suprafetei imprejmuite.
h2. Date de intrare
Fisierul de intrare $rezervatie.in$ contine pe prima linie numerele naturale L şi C. Pe linia a doua un sir de directii format doar din caracterele 'N', 'S', 'E', 'V', reprezentand dispunerea segmentelor (respectiv Nord, Sud, Est, Vest). Primul caracter din sir, reprezinta directia pe care se construieste primul segment si poate fi doar 'E' sau 'S'. Al i-lea caracter din sir, cu i cuprins între 2 si numarul de segmente, reprezinta directia pe care se construieste segmentul i, pornind din capatul liber al segmentului i-1. Pe linia a treia, se gaseste numarul natural N. Pe fiecare dintre urmatoarele N linii sunt cate doua numere naturale, reprezentand linia şi coloana corespunzatoare copacilor 1, 2, 3, ..., N.
Fisierul de intrare $rezervatie.in$ contine pe prima linie numerele naturale $L$ si $C$. Pe linia a doua un sir de directii format doar din caracterele $'N', 'S', 'E', 'V'$, reprezentand dispunerea segmentelor (respectiv Nord, Sud, Est, Vest). Primul caracter din sir, reprezinta directia pe care se construieste primul segment si poate fi doar $'E'$ sau $'S'$. Al $i$-lea caracter din sir, cu $i$ cuprins intre $2$ si numarul de segmente, reprezinta directia pe care se construieste segmentul $i$, pornind din capatul liber al segmentului $i-1$. Pe linia a treia, se gaseste numarul natural $N$. Pe fiecare dintre urmatoarele $N$ linii sunt cate doua numere naturale, reprezentand linia si coloana corespunzatoare copacilor $1, 2, 3, ..., N$.
h2. Date de iesire
In fisierul de iesire $rezervatie.out$ se va scrie pe prima linie un numar natural K, reprezentand numarul de copaci care se gasesc in interiorul imprejmuirii. Pe linia a doua, despartite prin cate un spatiu, se vor scrie K numere naturale in ordine crescatoare, reprezentand numerele de ordine ale copacilor aflati in interiorul suprafetei imprejmuite. In situatia in care niciun copac nu se gaseste in interiorul suprafetei imprejmuite, in fisierul de iesire se va afisa o singura valoare : 0.
In fisierul de iesire $rezervatie.out$ se va scrie pe prima linie un numar natural $K$, reprezentand numarul de copaci care se gasesc in interiorul imprejmuirii. Pe linia a doua, despartite prin cate un spatiu, se vor scrie $K$ numere naturale in ordine crescatoare, reprezentand numerele de ordine ale copacilor aflati in interiorul suprafetei imprejmuite. In situatia in care niciun copac nu se gaseste in interiorul suprafetei imprejmuite, in fisierul de iesire se va afisa o singura valoare : $0$.
h2. Restrictii
* $1 ≤ L, C ≤ 200$
* $1 ≤ N ≤ 1000$
* $4$ ≤ numarul de segmente ale imprejmuirii ≤ $1000$
* $4$ ≤ numarul de segmente ale imprejmuirii ≤ $10000$
h2. Exemplu
Datele de test de mai jos corespund figurilor 1 ÅŸi 2.
Datele de test de mai jos corespund figurilor $1$ si $2$.
table(example). |_. rezervatie.in |_. rezervatie.out |
| $5 4$
| 5 4
ESSENNEESVSSVVVNNN
$3$
$3 1$
$1 4$
$1 2$
| $2$
$1 2$
3
3 1
1 4
1 2
| 2
1 2
|
| $4 5$
| 4 5
SSSESENEEENNVSVVVNEENVVV
$4$
$4 2$
$3 4$
$2 3$
$1 1$
| $3$
$1 2 4$
4
4 2
3 4
2 3
1 1
| 3
1 2 4
|
== include(page="template/taskfooter" task_id="rezervatie") ==
