0601 - Dreptunghiuri

Cerința

Se consideră într-un reper cartezian n puncte cu coordonate pozitive. Prin fiecare punct se desenează o dreaptă verticală și una orizontală. Să se determine câte dreptunghiuri cu interioarele disjuncte s-au format prin intermediul acestor drepte şi al axelor de coordonate.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numărul n; următoarele n linii conțin câte două numere x y, reprezentând coordonatele punctelor.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie numărul C, reprezentând valoarea cerută.

Restricții și precizări

• 1 ≤ n ≤ 1000

Exemplul 1

input.txt:

4

1 0

2 4

4 2

1 2

output.txt:

6

Exemplul 2

input.txt:

9999999

1 0

3 4

4 2

1 2

Output:

Constrangeri neindeplinite

Rezolvare

<syntaxhighlight lang="python3" line="1"> def ver(n):

   if not(1<=n<=1000):
       print("Constrangeri neindeplinite")
       exit()
       

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:

   n = int(fin.readline())
   ver(n)
   a = [0] * (n + 1)
   b = [0] * (n + 1)

   for i in range(1, n + 1):
       a[i], b[i] = map(int, fin.readline().split())

   for i in range(1, n):
       for j in range(i + 1, n + 1):
           if a[i] > a[j]:
               a[i], a[j] = a[j], a[i]
           if b[i] > b[j]:
               b[i], b[j] = b[j], b[i]

   cnt1 = 0
   cnt2 = 0

   for i in range(1, n + 1):
       if a[i] != a[i - 1]:
           cnt1 += 1
       if b[i] != b[i - 1]:
           cnt2 += 1

   fout.write(str(cnt1 * cnt2))

</syntaxhighlight>