3660 - Unghi Drept

Cerinţa

Se dau n puncte în plan. O operație constă în alegerea unui triunghi dreptunghic și adăugarea unui punct, astfel încât cele 3 puncte alese și cel adăugat să formeze un nou dreptunghi. Aflați numărul maxim de operații ce se pot efectua.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n linii cu câte 2 numere naturale.

Date de ieșire

Programul va afișa pe ecran numărul cerut. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu respecta cerintele impuse." , iar daca se indeplinesc, se afiseaza mesajul "Datele de intrare respecta cerintele impuse."

Restricţii şi precizări

• 1 ≤ n ≤ 200.000
• celelalte numere citite vor fi mai mici decât 2.000.000.000

Exemplul 1

Intrare

4
1 3
2 3
1 2
3 3

Ieșire

Datele de intrare respecta cerintele impuse.
2

Explicație

La prima operație, alegem triungiul cu coordonatele (1, 2), (1, 3), (2, 3) și adăugăm punctul (2, 2) . La al doilea, alegem triunghiul cu coordonatele (2, 2), (2, 3), (3, 3) și adăugăm punctul (3, 2) . De aici, nu mai putem efectua nicio operație.

Exemplul 2

Intrare

0

Ieșire

Datele de intrare nu respecta cerintele impuse.

Rezolvare

<syntaxhighlight lang="python" line> def numar_maxim_operatii(puncte):

   coordonate_x = {}
   coordonate_y = {}

   for x, y in puncte:
       if x in coordonate_x:
           coordonate_x[x] += 1
       else:
           coordonate_x[x] = 1

       if y in coordonate_y:
           coordonate_y[y] += 1
       else:
           coordonate_y[y] = 1

   numar_operatii = 0

   for x, y in puncte:
       numar_operatii += (coordonate_x[x] - 1) * (coordonate_y[y] - 1)

   return numar_operatii

if __name__ == "__main__":

   try:
       n = int(input())

       if 1 <= n <= 200000:
           puncte = [tuple(map(int, input().split())) for _ in range(n)]

           if all(1 <= x <= 2000000000 and 1 <= y <= 2000000000 for x, y in puncte):
               rezultat = numar_maxim_operatii(puncte)
               print("Datele de intrare respecta cerintele impuse.")
               print(rezultat)
           else:
               print("Datele de intrare nu respecta cerintele impuse.")
       else:
           print("Datele de intrare nu respecta cerintele impuse.")

   except ValueError:
       print("Datele de intrare nu respecta cerintele impuse.")

</syntaxhighlight>