Editing 1103 - Harta

Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele <code>k</code> clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu <code>n•m</code> celule așezate pe <code>n</code> linii numerotate de la <code>1</code> la <code>n</code> și <code>m</code> coloane numerotate de la <code>1</code> la <code>m</code>.

Numim drum, un dreptunghi al tabloului care străbate întreaga localitate pe direcția Est-Vest și are un număr maxim de linii sau un dreptunghi care străbate întreaga localitate pe direcția Nord-Sud și are un număr maxim de coloane. Drumurile, evident, nu trebuie să treacă prin clădiri.

Cartografii sunt interesați ca pe această hartă să fie reprezentate la scară doar clădirile, nu și drumurile. De aceea, pentru realizarea hărții, lățimile drumurilor au fost reduse la o singură celulă

Tabloul care reprezintă imaginea localității se codifică astfel: <code>1</code> pentru o celulă ocupată de o clădire și <code>0</code> pentru o celulă neocupată.

= Cerinţe =
Cunoscând <code>n</code>, <code>m</code> și <code>k</code>, precum și tabloul care codifică imaginea, se cere să se determine:

'''1.''' Numărul <code>S</code> de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri <code>C</code> alese dintre celelalte <code>k – 1</code> clădiri, cu proprietatea că fiecare dintre ele “încape” în interiorul clădirii pătratice cu latură maximă, fără să se suprapună peste celulele marginale ale acesteia.

'''2.''' Tabloul care reprezintă harta, în urma prelucrării imaginii inițiale.

= Date de intrare =
Fişierul de intrare <code>harta.in</code> conţine pe prima linie un număr natural <code>p</code>. Pentru toate testele de intrare, numărul <code>p</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>.

Pe linia a doua se găsesc numerele naturale <code>n</code>, <code>m</code> și <code>k</code> separate prin câte un spațiu.

Pe fiecare dintre următoarele <code>k</code> linii, se găsesc câte patru numere naturale <code>i1 j1 i2 j2</code>

separate prin câte un spațiu, primele două numere reprezentând coordonatele celulei din extremitatea Nord-Vest, iar ultimele două, coordonatele celulei din extremitatea Sud-Est pentru fiecare dintre cele <code>k</code> clădiri.

= Date de ieșire =

* Dacă valoarea lui <code>p</code> este <code>1</code>, atunci se va rezolva numai cerința <code>1</code>. În acest caz, în fişierul de ieşire <code>harta.out</code> se vor scrie cele două numere <code>S</code> și <code>C</code> având semnificația descrisă la cerința <code>1</code>, separate printr-un singur spațiu.
* Dacă valoarea lui <code>p</code> este <code>2</code>, atunci se va rezolva numai cerința <code>2</code>. În acest caz, fişierul de ieşire <code>harta.out</code> va conține tabloul care reprezintă harta obținută pe baza imaginii din satelit. Fișierul va avea <code>n1</code> linii. Pe fiecare linie se vor găsi câte <code>m1</code> valori <code>0</code> sau <code>1</code> separate prin câte un singur spațiu. Celulele situate pe marginile clădirilor vor avea valoarea <code>1</code>. Celulele din interiorul clădirilor, ca și cele din exterior, vor avea valoarea <code>0</code>.

= Restricții și precizări =

* <code>3 ≤ n, m ≤ 1500</code>
* <code>1 ≤ i1 ≤ i2 ≤ n</code>
* <code>1 ≤ j1 ≤ j2 ≤ m</code>
* <code>1 ≤ k ≤ 1000</code>
* <code>1 ≤ Lmax ≤ 50</code> (<code>Lmax</code> – latura maximă a unui dreptunghi)
* Se garantează că există soluție pentru ambele cerințe, pentru toate datele de test.
* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

= Exemplul 1 =
<code>harta.in</code>
 1
 7 7 4
 1 1 4 4
 6 2 6 4
 3 6 3 6
 6 6 7 7
<code>harta.out</code>
 16 2

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import numpy as np


#define pb push_back
#define DIM 1501
typedef vector<int> VI;

d = []
xa = []
ya = []
x = [0]
y = [0]
s1 = [True]
s2 = [True]
c1 = []
c2 = []
b1 = []
b2 = []
k = 0
N = 0
M = 0
n = 0
m = 0
Lmax = 0
L = 0
H = 0
T = 0
nr_dr = 0
A = np.zeros((1501, 1501), dtype=bool)

def GetPos(v, val):
    n = len(v)
    lo = 0
    hi = n
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if v[mid] == val:
            return mid
        if val < v[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    return 0

def WriteMatr(a, N, M):
    for i in range(1, N+1):
        for j in range(1, M+1):
            fout.write(str(int(a[i][j])) + ' ')
        fout.write('\n')

with open("harta.in", "r") as fin:
    lines = fin.readlines()
    T, N, M, k = map(int, lines[0].split())
    imax = 0
    jmax = 0
    for i in range(k):
        i1, j1, i2, j2 = map(int, lines[i+1].split())
        d.append((i1, j1, i2, j2))
        L = i2 - i1 + 1
        H = j2 - j1 + 1
        if L == H and L > Lmax:
            Lmax = L
        for i in range(i1, i2+1):
            xa.extend([i, i])
            ya.extend([j1, j2])
            if not s1[i]:
                x.append(i)
                s1[i] = True
        for j in range(j1, j2+1):
            xa.extend([i1, i2])
            ya.extend([j, j])
            if not s2[j]:
                y.append(j)
                s2[j] = True
        if not s1[i1 - 1]:
            x.append(i1 - 1)
            s1[i1 - 1] = True
        if not s2[j1 - 1]:
            y.append(j1 - 1)
            s2[j1 - 1] = True
        imax = max(imax, i2)
        jmax = max(jmax, j2)
    if T == 1:
        for i in range(k):
            L = d[i][2] - d[i][0] + 1
            H = d[i][3] - d[i][1] + 1
            if L < Lmax - 1 and H < Lmax - 1:
                nr_dr += 1
        fout.write(str(Lmax * Lmax) + ' ' + str(nr_dr) + '\n')
    else:
        c1 = [0] * (imax + 1)
        c2 = [0] * (jmax + 1)
        for i in range(len(x)):
            c1[x[i]] += 1
        for i in range(len(y)):
            c2[y[i]] += 1
        for i in range(1, imax+1):
            c1[i] += c1[i - 1]
        for i in range(1, jmax+1):
            c2[i] += c2[i - 1]
        b1 = [0] * len(x)
        b2 = [0] * len(y)
        for i in range(len(x)):
            b1[c1[x[i]] - 1] = x[i]
            c1[x[i]] -= 1
        for i in range(len(y)):
            b2[c2[y[i]] - 1] = y[i]
            c2[y[i]] -= 1
        n = 0
        m = 0
        for k in range(len(xa)):
            i = GetPos(b1, xa[k])
            j = GetPos(b2, ya[k])
            n = max(n, i)
            m = max(m, j)
            A[i][j] = True
        if n < M:
            n += 1
        if m < M:
            m += 1
        WriteMatr(A, n, m)
</syntaxhighlight>