2170 - Dreptc

Enunt

Se consideră n puncte colorate dispuse în plan. Ele sunt identificate prin coordonatele 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ătoare 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ţa

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șierului 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. Nu există două puncte cu aceleași coordonate.

Date de ieșire

Fișierul de ieșire dreptc.out va conține un singur număr reprezentând numărul maxim de dreptunghiuri corecte.

Restricţii şi precizări

• 1 ≤ N ≤ 1000
• 1 ≤ C ≤ 5
• -1000 ≤ x , y ≤ 1000
• 40% din teste vor avea N ≤ 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).

Rezolvare

<syntaxhighlight lang="python" line> def count_rectangles(points):

   n = len(points)
   rectangles = 0

   # Generate all possible rectangles
   for i in range(n):
       for j in range(i + 1, n):
           # Check if the other two points of the potential rectangle exist and have the same color
           x1, y1, c1 = points[i]
           x2, y2, c2 = points[j]
           if (x1, y2, c1) in points and (x2, y1, c1) in points and c1 == c2:
               rectangles += 1

   return rectangles // 2  # Each rectangle is counted twice, so we divide by 2

def main():

   # Read input
   with open("dreptc.in", "r") as fin:
       n, maxc = map(int, fin.readline().split())
       points = [tuple(map(int, fin.readline().split())) for _ in range(n)]

   # Count rectangles
   result = count_rectangles(points)

   # Write output
   with open("dreptc.out", "w") as fout:
       fout.write(str(result) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>