== include(page="template/taskheader" task_id="radio") ==
Poveste si cerinta...
Pe suprafata Romaniei exista $K$ statii radio pozitionate la coordonate si altitudini diferite. Fiecare dintre aceste statii are o anumita raza de transmisie, adica o distanta maxima pana la care poate trimite semnalul radio. Guvernul dorste sa amplaseze o antena radio undeva pe harta, in asa fel incat sa receptioneze semnalele tuturor celor $K$ statii radio (adica distanta pana la fiecare statie radio sa fie mai mica sau egala cu raza de transmisie a statiei respective).
Harta Romaniei poate fi privita ca o matrice cu $M$ linii si $N$ coloane, unde valoarea de pe linia $i$ si coloana $j$ reprezinta altitudinea zonei respective. Lungimea laturii unui patrat din matrice este $1$. Toate cele $K$ statii radio sunt amplasate in zone distincte de pe harta si la inaltimea corespunzatoare zonei unde sunt amplasate. In plus, ele sunt pozitionate exact in centrul zonei (in centrul patratelului respectiv din matrice). Antena radio poate fi amplasata in centrul oricarei zone care in care nu se afla o statie radio, la aceeasi altitudine cu cea a zonei sau la o altitudine mai mare (dar care sa fie neaparat un numar intreg).
Determinati cate posibilitati de amplasare a antenei radio exista. Daca antena poate fi amplasata in centrul zonei de pe linia $i$ si coloana $j$ la altitudinile $h1$ si $h2$ (cu $h1 <> h2$), acestea sunt considerate doua posibilitati diferite.
h2. Date de intrare
...
Prima linie a fisierului de intrare $radio.in$ contine $3$ numere intregi, separate prin cate un spatiu: $M$, $N$ si $K$. $M$ si $N$ reprezinta numarul de linii si de coloane ale hartii, iar $K$ reprezinta numarul de statii radio. Urmatoarele $M$ linii contin cate $N$ numere intregi, reprezentand altitudinile zonelor respective de pe harta. Dupa aceasta, urmeaza $K$ linii, fiecare continand cate $3$ numere, separate prin cate un spatiu: $i$, $j$ si $R$. $i$ si $j$ reprezinta linia si coloana zonei in care este amplasata o statie radio, iar $R$ reprezinta raza de transmisie a statiei respective. $i$ si $j$ sunt numere intregi, iar $R$ este un numar real.
h2. Date de iesire
...
In fisierul de iesire $radio.out$ veti afisa numarul total de posibilitati de a amplasa antena radio pe harta.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 50$
* $1 ≤ K ≤ min{M*N-1, 1000}$
* $0 ≤ inaltimea oricarei zone ≤ 32 000$
* Nu vor exista $2$ statii radio amplasate in aceeasi zona de pe harta.
* La calculul distantelor, aveti grija ca sunt distante intr-un spatiu 3D.
h2. Exemplu
table(example). |_. radio.in |_. radio.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 5 3
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
6 7 8 9 10
5 4 3 2 1
1 1 4.3
5 5 4.3
5 1 4.3
|4
|
h3. Explicatie
...
Antena radio poate fi amplasata in zona de pe linia $3$ si coloana $2$, la aceeasi inaltime cu cea a zonei sau la o inaltime cu $1$ mai mare. De asemenea, antena radio poate fi amplasata in zona de pe linia $3$ si coloana $3$, la aceeasi inaltime cu cea a zonei sau la o inaltime cu $1$ mai mare.
== include(page="template/taskfooter" task_id="radio") ==
