Simulare OJI 2007 clasa a 8-a | dreptc

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: dreptc.in Output: dreptc.out

Se consideră NN 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 11 și CC 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 NN puncte din plan.

Date de intrare

Pe prima linie a fișierul text dreptc.in se găsesc două numere N,MaxCN, MaxC reprezentând numărul de puncte din plan și numărul de culori asociate punctelor. Pe următoarele NN linii se citesc câte trei numere x y cx \ 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

  • 1N1 0001 \leq N \leq 1 \ 000;
  • 1C51 \leq C \leq 5;
  • 1 000x,y1 000-1 \ 000 \leq x, y \leq 1 \ 000;
  • Nu există două puncte cu aceleași coordonate
  • 4040% din teste vor avea N100N \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, 4), (6, 4), (6, 0)
(3,0),(3,10),(6,10),(6,0)(3, 0), (3,10), (6,10), (6, 0)
(3,6),(3,10),(6,10),(6,4)(3, 6), (3,10), (6,10), (6, 4)

Log in or sign up to be able to send submissions!