== include(page="template/taskheader" task_id="ape") ==
Mihai crede că mă pricep la informatică şi mă roagă să îl ajut la efectuarea unor calcule. Mi-a povestit că în vacanţă a fost la ţară la bunici. Bunicii lui se ocupă de piscicultură şi au preluat spre utilizare o zonă de teren unde se află lacuri, heleştee şi bălţi. Sunt plătite taxe speciale în funcţie de suprafeţele acestor ape. Bunicului i se pare că cei de la oficiul unde se plătesc taxele au date greşite în dosare, despre ariile acestor suprafeţe de apă şi l-a rugat pe Mihai să îi calculeze cu aproximaţie aceste arii. Mihai a studiat problema şi s-a hotărât să înconjoare fiecare apă, mergând pe conturul acesteia. Pasul lui are lungimea de 1 metru. La fiecare pas Mihai foloseşte o busolă şi îşi notează într-un carneţel direcţia înspre care a fost efectuat pasul Nord, Sud, Est sau Vest. După fiecare pas Mihai actualizează şi numărul de paşi pe care i-a făcut.
Mihai crede că mă pricep la informatică şi mă roagă să îl ajut la efectuarea unor calcule. Mi-a povestit că în vacanţă a fost la ţară la bunici. Bunicii lui se ocupă de piscicultură şi au preluat spre utilizare o zonă de teren unde se află lacuri, heleştee şi bălţi. Sunt plătite taxe speciale în funcţie de suprafeţele acestor ape. Bunicului i se pare că cei de la oficiul unde se plătesc taxele au date greşite în dosare, despre ariile acestor suprafeţe de apă şi l-a rugat pe Mihai să îi calculeze cu aproximaţie aceste arii. Mihai a studiat problema şi s-a hotărât să înconjoare fiecare apă, mergând pe conturul acesteia. Pasul lui are lungimea de un metru. La fiecare pas Mihai foloseşte o busolă şi îşi notează într-un carneţel direcţia înspre care a fost efectuat pasul Nord, Sud, Est sau Vest. După fiecare pas Mihai actualizează şi numărul de paşi pe care i-a făcut.
Se doreşte să se afle, pentru fiecare traseu :
a) Dimensiunile pe direcţiile Vest-Est şi respectiv Nord-Sud ale unei suprafeţe dreptunghiulare de arie minimă care cuprinde în interior sau pe margini suprafaţa apei.
b) Sensul în care a fost parcurs traseul: 0- pentru sens orar, respectiv 1- pentru sens invers orar;
c) Aria suprafeţei apei înconjurate, din interiorul traseului.
Se doreşte să se afle, pentru fiecare traseu:
* Dimensiunile pe direcţiile Vest-Est şi respectiv Nord-Sud ale unei suprafeţe dreptunghiulare de arie minimă care cuprinde în interior sau pe margini suprafaţa apei.
* Sensul în care a fost parcurs traseul: {$0$} - pentru sens orar, respectiv $1$ - pentru sens invers orar;
* Aria suprafeţei apei înconjurate, din interiorul traseului.
h2. Date de intrare
Fişierul de intrare ape.in are pe prima linie numărul $P$ de paşi ai traseului. În linia 2 se află un şir de $P$ litere mari, fără spaţii între ele, din mulţimea {N,S,E,V} reprezentând traseul.
Fişierul de intrare $ape.in$ are pe prima linie numărul $P$ de paşi ai traseului. În linia 2 se află un şir de $P$ litere mari, fără spaţii între ele, din mulţimea ${N,S,E,V}$ reprezentând traseul.
h2. Date de ieşire
Fişierul de ieşire ape.out va conţine patru numere naturale separate prin câte un spaţiu: primul număr reprezintă dimensiunea pe direcţia Vest - Est şi al doilea număr reprezintă dimensiunea pe direcţia Nord–Sud a suprafeţei dreptunghiulare de arie minimă care cuprinde în interior sau pe margini suprafaţa apei delimitată de traseu; al treilea număr reprezintă sensul parcurgerii, iar al patrulea număr reprezintă aria.
Fişierul de ieşire $ape.out$ va conţine patru numere naturale separate prin câte un spaţiu: primul număr reprezintă dimensiunea pe direcţia Vest - Est şi al doilea număr reprezintă dimensiunea pe direcţia Nord–Sud a suprafeţei dreptunghiulare de arie minimă care cuprinde în interior sau pe margini suprafaţa apei delimitată de traseu; al treilea număr reprezintă sensul parcurgerii, iar al patrulea număr reprezintă aria.
h2. Restricţii
* $1 ≤ P ≤ 10000$
* Pentru 30% din teste traseele vor avea lungimea maximă 2000.
* Dacă dimensiunile suprafeţei dreptunghiulare de arie minimă sunt corecte, atunci se va acorda 10% din punctaj/test.
* Dacă sensul traseului este determinat corect, atunci se vor primi 10% puncte/test.
* Pentru $30%$ din teste traseele vor avea lungimea maximă $2000$.
* Dacă dimensiunile suprafeţei dreptunghiulare de arie minimă sunt corecte, atunci se va acorda $10%$ din punctaj/test.
* Dacă sensul traseului este determinat corect, atunci se vor primi $10%$ puncte/test.
* Aria suprafeţei apei este un număr natural nenul.
h2. Exemplu
h3. Explicaţie
Căsuţele marcate cu ‘-‘ reprezintă traseul, iar pătratele negre reprezintă apa.
!>problema/ape?ape.jpg!
Căsuţele marcate cu $-$ reprezintă traseul, iar pătratele negre reprezintă apa.
Zona mărginită de linia îngroşată reprezintă suprafaţa dreptunghiulară minimală ce conţine pătratele negre, care reprezintă apa.
Căsuţa marcată cu * este poziţia de pornire.
Exemplu corespunde imaginii de mai jos.
Căsuţa marcată cu $*$ este poziţia de pornire.
Exemplu corespunde imaginii alăturate.
!problema/ape?ape.jpg
== include(page="template/taskfooter" task_id="ape") ==
