Alexandra Leș: Pagină nouă: == Cerinţa == Se dau '''n''' puncte distincte în plan, de coordonate întregi. Aflați numărul maxim de puncte aflate în interiorul sau pe laturile unui pătrat de latură '''k''', având vârfurile de coordonate întregi și laturile paralele cu axele de coordonate. == Date de intrare == Fișierul de intrare '''pct.in''' conține pe prima linie numerele '''n''' și '''k''', iar pe a doua linie '''n''' perechi de numere întregi reprezentând coordonatele punctelor, separ...

2023-04-28T12:52:37Z

Pagină nouă: == Cerinţa == Se dau '''n''' puncte distincte în plan, de coordonate întregi. Aflați numărul maxim de puncte aflate în interiorul sau pe laturile unui pătrat de latură '''k''', având vârfurile de coordonate întregi și laturile paralele cu axele de coordonate. == Date de intrare == Fișierul de intrare '''pct.in''' conține pe prima linie numerele '''n''' și '''k''', iar pe a doua linie '''n''' perechi de numere întregi reprezentând coordonatele punctelor, separ...

New page

== Cerinţa ==
Se dau '''n''' puncte distincte în plan, de coordonate întregi. Aflați numărul maxim de puncte aflate în interiorul sau pe laturile unui pătrat de latură '''k''', având vârfurile de coordonate întregi și laturile paralele cu axele de coordonate.
== Date de intrare ==
Fișierul de intrare '''pct.in''' conține pe prima linie numerele '''n''' și '''k''', iar pe a doua linie '''n''' perechi de numere întregi reprezentând coordonatele punctelor, separate prin spații.
== Date de ieşire ==
Dacă datele sunt introduse corect,în fişierul de ieşire '''pct.out''' se va afișa :'''"Datele sunt introduse corect."''',apoi pe un rând nou va conţine numărul maxim de puncte situate în interiorul sau pe laturile unui pătrat de latură k.În cazul contrar,se va afișa pe ecran '''"Datele nu corespund restricțiilor impuse."'''.
== Restricții și precizări ==
* 1 &les; n &les; 100.000
* 2 &les; k &les; 1000
*coordonatele punctelor sunt cuprinse între 0 și 1000, inclusiv
== Exemplu ==
; pct.in
: 3 2
: 1 1
: 1 0
: 3 4
; pct.out
: Datele sunt introduse corect.
: 2
== Explicație ==
Se poate alege pătratul de latură '''2''', având vârful stânga-jos de coordonate '''(0,0)'''.
== Rezolvare ==
<syntaxhighlight lang="python" line>

#Funcție care verifică dacă datele de intrare sunt valide, conform restricțiilor problemei.
def validare(n, k, puncte):

if not (1 <= n <= 100000): # n trebuie să fie între 1 și 100000
return False
if not (2 <= k <= 1000): # k trebuie să fie între 2 și 1000
return False
for x, y in puncte: # fiecare punct trebuie să aibă coordonate între 0 și 1000
if not (0 <= x <= 1000 and 0 <= y <= 1000):
return False
return True

#Funcție care află numărul maxim de puncte situate în interiorul sau pe laturile unui pătrat de latură k.
def rezolvare(n, k, puncte):

a = [[False] * 1002 for _ in range(1002)] # matricea a reține dacă există puncte la coordonatele (i, j)
sp = [[0] * 1002 for _ in range(1002)] # matricea sp reține suma punctelor dintr-un dreptunghi format de (1, 1) și (i, j)
lin = col = 0 # variabilele lin și col rețin coordonatele maxime ale punctelor

# parcurgerea listei de puncte
for x, y in puncte:
a[x + 1][y + 1] = True # marchează existența punctului la coordonatele (x+1, y+1)

if lin < x:
lin = x # actualizează coordonata maximă pe linii

if col < y:
col = y # actualizează coordonata maximă pe coloane

# parcurgerea matricii sp și calcularea sumelor
for i in range(1, lin+1):
for j in range(1, col+1):
sp[i][j] = sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1] + a[i][j]

maxi = 0 # variabila maxi reține numărul maxim de puncte găsit până acum

# parcurgerea matricii sp și găsirea numărului maxim de puncte
for i in range(1, lin+1):
for j in range(1, col+1):
linie_dr = i + k
coloana_dr = j + k
if linie_dr <= lin and coloana_dr <= col:
puncte = sp[linie_dr][coloana_dr] - sp[linie_dr][j-1] - sp[i-1][coloana_dr] + sp[i-1][j-1]
if maxi < puncte:
maxi = puncte

return maxi

#Funcția principală
if __name__ == '__main__':
with open('pct.in', 'r') as f:

n, k = map(int, f.readline().split())
puncte = [tuple(map(int, linie.split())) for linie in f.readlines()]

if validare(n, k, puncte):
rezultat = rezolvare(n, k, puncte)

with open('pct.out', 'w') as f:
f.write('Datele sunt introduse corect.\n')
f.write(str(rezultat))
else:
with open('pct.out', 'w') as f:
f.write('Datele nu corespund restricțiilor impuse.\n')

</syntaxhighlight>

3483 - Pct - Revision history