Simulare OJI 2007 clasa a 8-a | 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:

• 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.

Cerință

Să se determine numărul maxim de dreptunghiuri corecte care se pot forma cu cele $N$ puncte din plan.

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.

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.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• $1 \leq C \leq 5$;
• $-1 \ 000 \leq x, y \leq 1 \ 000$;
• Nu există două puncte cu aceleași coordonate
• $40$% din teste vor avea $N \leq 100$;

Exemplu

dreptc.in

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

dreptc.out

3

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, 6), (3,10), (6,10), (6, 4)$