AjM: Pagină nouă: == 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...

2024-06-03T17:39:19Z

Pagină nouă: == 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...

New page

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

2170 - Dreptc - Revision history