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

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