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

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

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

1. 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

1. 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")

</syntaxhighlight>