3483 - Pct

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 ⩽ n ⩽ 100.000
• 2 ⩽ k ⩽ 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>

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

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

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