== include(page="template/taskheader" task_id="dreptc") ==
Se consideră $N$ puncte colorate dispuse în plan. Ele sunt identificate prin coordontele lor întregi, pe axele $OX$ și [$OY$]. Fiecare punct are asociat un număr natural între $1$ și $C$ reprezentând codul culorii lui. Un dreptunghi se numește corect dacă îndeplinește simultan următoarele condiții:
Se consideră n puncte colorate dispuse în plan. Ele sunt identificate prin coordontele lor întregi, pe axele OX și OY. Fiecare punct are asociat un număr natural între 1 și C reprezentând codul culorii lui. Un dreptunghi se numește corect dacă îndeplinește simultan următoarele condiții:
toate cele patru vârfuri se regăsesc printre cele n puncte date;
are laturile paralele cu axele OX, OY;
are vârfurile colorate în aceeași culoare.
* toate cele patru vârfuri se regăsesc printre cele $N$ puncte date;
* are laturile paralele cu axele [$OX$], [$OY$];
* are vârfurile colorate în aceeași culoare.
Cerinta:
h2. Cerinta:
Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele n puncte din plan.
Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele $N$ puncte din plan.
h2. Date de intrare
Pe prima linie a fișierul text $dreptc.in$ se găsesc două numere [$N$], $MaxC$ reprezentând numărul de puncte din plan și numărul de culori asociate punctelor. Pe următoarele $N$ linii se citesc câte trei numere $x$ $y$ $c$ reprezentând în ordine coordonata pe axa $OX$ (abscisa), coordonata pe axa $OY$ (ordonata) și codul culorii asociate punctului.
Fișierul de intrare $dreptc.in$ ...
h2. Date de ieșire
Pe prima linie a fișierul text dreptc.out se va scrie un singur număr cu semnificația numărul maxim de dreptunghiuri corecte.
În fișierul de ieșire $dreptc.out$ ...
h2. Restricții
* $1 ≤ N ≤ 1 000$
* $1 ≤ C ≤ 5$
* $-1 000 ≤ x, y ≤ 1 000$
* Nu există două puncte cu aceleași coordonate
* $40%$ din teste vor avea $N ≤ 100$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
table(example).
|_. dreptc.in |_. dreptc.out |
| 9 2
3 10 1
3 8 2
3 6 1
3 4 1
3 0 1
6 0 1
6 4 1
6 8 2
6 10 1
| 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
Vârfurile celor trei dreptunghiuri corecte sunt:
* (3, 0), (3, 4), (6, 4), (6, 0)
* (3, 0), (3,10), (6,10), (6, 0)
* (3, 4), (3,10), (6,10), (6, 4)
...
== include(page="template/taskfooter" task_id="dreptc") ==
