Vizualizare sursă pentru „2071 - Triunghiuri2”

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

= Cerința =
Cunoscând <code>N</code> și coordonatele celor <code>N</code> 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 <code>OX</code>;
* nu au laturi paralele cu <code>OY</code>;

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

= Date de ieșire =
Fișierul <code>output.txt</code> va avea următoarea structură:

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

= Restricții și precizări =

* <code>3 ≤ N ≤ 100 000</code>

== 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ă: <code>(3, 4)</code> și <code>(3,2)</code>.

== 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 <code>4</code> triunghiuri care satisfac cerințele. Dacă notăm cele <code>5</code> puncte din fișier cu <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code>, <code>E</code> (ca în imagine), atunci, cele <code>4</code> triunghiuri care satisfac cerințele sunt : <code>ABC</code>, <code>ACE</code>, <code>ABE</code> și <code>BDE</code>.

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

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

</syntaxhighlight>