Miawinator: Pagină nouă: 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ă par...

2024-01-04T23:28:58Z

Pagină nouă: 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ă par...

New page

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>

2071 - Triunghiuri2 - Revision history