2071 - Triunghiuri2

Se consideră N puncte din plan, având coordonate numere naturale, relativ la un reper cartezian XOY, oricare două puncte fiind distincte.

Cerința

Cunoscând N și coordonatele celor N puncte, să se determine:

1) Numărul maxim de puncte care au aceeași abscisă.

2) Numărul triunghiurilor care se pot desena respectând următoarele condiții:

• au toate vârfurile în puncte dintre cele date;
• au o latură paralelă cu OX;
• nu au laturi paralele cu OY;

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numărul p, care indică cerința ce trebuie rezolvată (p are valoarea 1 sau 2). Pe a doua linie se află numărul natural N, reprezentând numărul punctelor date. Pe următoarele N linii se găsesc câte două valori naturale x y, separate prin câte un spațiu, reprezentând coordonatele punctelor date.

Date de ieșire

Fișierul output.txt va avea următoarea structură:

• Dacă p = 1 se va scrie în fișier, pe prima linie, numărul maxim de puncte care au aceeași abscisă (cerința 1).
• Dacă p = 2 se va scrie în fișier, pe prima linie, numărul triunghiurilor care se pot desena respectând condițiile date, modulo 1.000.003, adică restul împărțirii numărului de triunghiuri la 1 000 003 (cerința 2).

Restricții și precizări

• 3 ≤ N ≤ 100 000

Exemplul 1

input.txt:

1

5

2 1

1 4

3 4

3 2

6 4

output.txt:

2

Explicație:

Se rezolvă cerința 1). Sunt maximum două puncte care au aceeași abscisă: (3, 4) și (3,2).

Exemplul 2

input.txt:

2

5

2 1

1 4

3 4

3 2

6 4

output.txt:

4

Explicație:

Se rezolvă cerința 2). Se pot trasa 4 triunghiuri care satisfac cerințele. Dacă notăm cele 5 puncte din fișier cu A, B, C, D, E (ca în imagine), atunci, cele 4 triunghiuri care satisfac cerințele sunt : ABC, ACE, ABE și BDE.

Exemplul 3

input.txt:

2

9999999999999

2 1

1 4

3 4

3 2

6 4

Output:

Input-ul nu convine conditiilor

Rezolvare

def verificare(n):
    if not(3<=n<=100000):
        print("Input-ul nu convine conditiilor")
        exit()

# Define constants
Nmax = 100001  # numarul maxim de puncte
Cmax = 1001    # coordonata maxima
IN = "input.txt"
OU = "output.txt"

N = 0  # numarul punctelor
NrTr = 0  # numarul triunghiurilor gasite

nx = [0] * Cmax  # nx[i] - cate puncte sunt pe absisa i
ny = [0] * Cmax  # ny[i] - cate puncte sunt pe ordonata i
H = [[0] * Cmax for _ in range(Cmax)]  # memorez punctele ordonate H[i] - lista punctelor cu ordonata i

# citire date
with open(IN, "r") as Fin:
    V = int(Fin.readline())
    N = int(Fin.readline())
    verificare(N) 
    for i in range(Cmax):
        nx[i] = ny[i] = 0
    for _ in range(N):
        x, y = map(int, Fin.readline().split())
        nx[x] += 1
        ny[y] += 1
        H[y][ny[y]] = x

if V == 1:
    Max = max(nx[:1000])
    with open(OU, "w") as Fou:
        Fou.write(f"{Max}\n")
else:
    NrTr = 0
    for i in range(Cmax - 1):
        if ny[i] > 1:
            sumLin = 0
            for j in range(1, ny[i] + 1):
                sumLin += (nx[H[i][j]] - 1) * (ny[i] - 1)
            aux1 = (ny[i] * (ny[i] - 1) // 2)
            aux2 = (N - ny[i])
            aux = aux1 * aux2
            NrTr += aux - sumLin
            NrTr %= 1000003

    with open(OU, "w") as Fou:
        Fou.write(f"{NrTr}\n")