Editing 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
<br>

== 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>