Fișierul intrare/ieșire	dreptc.in, dreptc.out	Sursă	OJI 2007 clasa a 8-a
Autor		Adăugată de	Pacurar Alexandru • Alex.P
Timp de execuție pe test	0.1 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Dreptc (clasa a 8-a)

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.

Cerinta:

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

• 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

Exemplu

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)