1209 - T Drept

Enunț

Se consideră N puncte de coordonate întregi în sistemul de coordonate cartezian.

Cerința

Scrieţi un program care determină numărul de triunghiuri dreptunghice având vârfurile plasate în 3 dintre punctele date şi catetele respectiv paralele cu axele de coordonate.

Date de intrare

Fișierul de intrare tdreptin.txt conține pe prima linie numărul natural N, care reprezintă numărul de puncte. Pe următoarele N linii se află câte două numere naturale x y, separate prin spaţiu, reprezentând coordonatele carteziene ale celor N puncte (abscisa şi ordonata).

Date de ieșire

Fișierul de ieșire tdreptout.txt va conține o singură linie pe care va fi scris un număr natural reprezentând numărul de triunghiuri dreptunghice care respectă condiţiile din enunţ. Deoarece numărul de soluţii poate fi foarte mare, rezultatul va fi afişat modulo 666013 (adică restul împărţirii rezultatului la 666013).

Restricții și precizări

• 3 ⩽ N ⩽ 100.000
• 0 ⩽ x, y ⩽ 100.000
• Cele N puncte din fişierul de intrare sunt distincte două câte două.

Exemplul 1

Intrare

tdreptin.txt

8

1 1

1 4

10 8

4 1

9 1

5 5

7 4

7 5

Ieșire

Datele de intrare corespund restricțiilor impuse

tdreptout.txt

5

Explicație

Triunghiurile dreptunghice formate sunt:

(1,1) (1,4) (4,1)
(1,1) (9,1) (1,4)
(5,5) (7,4) (7,5)
(1,4) (7,4) (7,5)
(1,1) (1,4) (7,4)

Exemplul 2

Intrare

tdreptin.txt

2

1 1

1 4

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1209 - TDrept

def validare_date(x, y):
    return 3 <= len(x) <= 100000 and all(0 <= xi <= 100000 and 0 <= yi <= 100000 for xi, yi in zip(x, y))


def numar_triunghiuri_dreptunghice(x, y):
    n = len(x)
    rezultat = 0

    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if (x[i] == x[j] or x[j] == x[k] or x[i] == x[k]) and \
                   (y[i] == y[j] or y[j] == y[k] or y[i] == y[k]):
                    rezultat += 1
    return rezultat % 666013


def citire_date():
    with open("tdreptin.txt", "r") as f:
        n = int(f.readline().strip())
        x = []
        y = []
        for _ in range(n):
            xi, yi = map(int, f.readline().split())
            x.append(xi)
            y.append(yi)
    return n, x, y


def scrie_rezultat(rezultat):
    with open("tdreptout.txt", "w") as f:
        f.write(str(rezultat))


if __name__ == "__main__":
    n, x, y = citire_date()

    if validare_date(x, y):
        print("Datele de intrare corespund restricțiilor impuse")
        rezultat = numar_triunghiuri_dreptunghice(x, y)
        scrie_rezultat(rezultat)
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)