Editing 3483 - Pct (section)

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