View source for 0601 - Dreptunghiuri

= Cerința =
Se consideră într-un reper cartezian <code>n</code> 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 <code>input.txt</code> conține pe prima linie numărul <code>n</code>; următoarele <code>n</code> linii conțin câte două numere <code>x y</code>, reprezentând coordonatele punctelor.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>

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