Fişierul intrare/ieşire:	robotics.in, robotics.out	Sursă	ONI 2015, clasa a 10-a
Autor	Eugen Nodea	Adăugată de	Puscas Sergiu •harababurel
Timp execuţie pe test	0.025 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Robotics

Ne aflăm în secţia de vopsitorie a uzinei Toyota Motor unde inginerii japonezi prezintă ultimul tip de robot industrial de vopsire. În dorinţa de a
evidenţia calitatea şi viteza de execuţie a roboţilor, inginerii folosesc pentru demonstraţie o tablă de dimensiunea $n \times n$ , împărţită în pătrate cu latura egală cu $1$ , reprezentată sub forma unui tablou bidimensional cu $n$ linii şi $n$ coloane.

Un robot utilizat pentru vopsire are două braţe telescopice care se deplasează de-a lungul unei axe. Fiecare braţ poate vopsi într-o unitate de timp un singur pătrat. La momentul de timp $t=0$ robotul primeşte comanda de a se poziţiona într-un pătrat specificat prin coordonatele $\left ( x, y \right )$ .

În funcţie de traiectoria de deplasare roboţii folosiţi sunt de două tipuri. La momentul de timp $t$ robotul de tip $1$ vopseşte pătratele aflate la coordonatele: $\left ( x-t, y+t \right )$ şi $\left ( x+t, y-t \right )$ , iar robotul de tip $2$ vopseşte pătratele aflate la coordonatele: $\left ( x+t, y+t \right )$ şi $\left ( x-t, y-t \right )$ . Pentru vopsirea unui pătrat se consumă un litru de vopsea. Pe tablă sunt aşezaţi $m$ roboţi.

Cerinţe

Cunoscând pentru cei $m$ roboţi coordonatele iniţiale $(x_{i}, y_{i}), i \in \left \{ 1, 2, ..., m \right \}$ se cere să se determine:

Cantitatea totală de vopsea care a fost folosită de roboţi după $t$ unităţi de timp.
Numărul minim de unităţi de timp necesare formării primului dreptunghi cu arie nenulă. Un dreptunghi corect format este rezultatul intersecţiei a două traiectorii paralele a doi roboţi de tip $1$ cu două traiectorii paralele a doi roboţi de tip $2$ , iar colţurile dreptunghiului sunt $4$ pătrate care au fost vopsite de doi roboţi de tipuri diferite.

Date de intrare

Fişierul de intrare robotics.in conţine pe prima linie trei valori naturale nenule $n$ , $m$ şi $t$ , cu semnificaţiile din enunţ, despărţite prin câte un singur spaţiu.
Pe fiecare dintre următoarele $m$ linii se află câte trei valori naturale nenule $x_{i}$ , $y_{i}$ şi $z_{i}$ , despărţite prin câte un spaţiu, unde: $x_{i}, y_{i}$ reprezintă coordonatele iniţiale unde se poziţionează robotul $i$ , iar $z_{i}$ reprezintă tipul robotului.

Date de ieşire

Fişierul de ieşire robotics.out va avea două linii.
Prima linie conţine un număr natural $C$ nenul ce reprezintă cantitatea totală de vopsea care este folosită de roboţi după $t$ unităţi de timp.
A doua linie conţine un număr natural nenul $T_{min}$ ce reprezintă numărul minim de unităţi de timp necesare formării primului dreptunghi de arie nenulă.

Restricţii

1 ≤ t < n ≤ 1 000
1 ≤ m ≤ 2*n
1 ≤ x, y ≤ n
Coordonatele celor $m$ roboţi sunt distincte două câte două.
Doi roboţi nu se pot afla pe aceeaşi traiectorie la un moment dat.
La momentul $t=0$ robotul se poziţionează în pătratul specificat prin coordonatele $(x, y)$ şi vopseşte o singură dată acest pătrat.
Doi roboţi de tipuri diferite care ajung în acelaşi timp pe un pătrat pot vopsi simultan pătratul.
Dacă braţul unui robot părăseşte tabla dreptunghiulară, braţul îşi încetează activitatea.
Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.

Exemplu

robotics.in	robotics.out
13 3 6 3 5 1 7 5 2 7 9 1	29 0
19 9 4 4 5 1 4 14 2 2 11 1 14 7 2 5 10 2 14 13 1 7 4 2 7 10 1 12 13 2	75 3

Explicaţie

În primul exemplu:
- Cantitatea de vopsea care este folosită de roboţi după $t$ unităţi de timp este $29$ .
- Nu se pot forma dreptunghiuri.

În al doilea exemplu:
- Cantitatea de vopsea care este folosită de roboţi după $t$ unităţi de timp este $75$ .
- Singurele dreptunghiuri corect formate după au colţurile în pătratele de coordonate:
  - $(2,7),\:(6,11),\:(10,7),\:(6,3)$ , respectiv
  - $(8,9),\:(13,14),\:(17,10),\:(12,5)$ .
- Observăm faptul că primul dreptunghi se formează după $t=3$ (timpul minim)