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 k clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub forma unui tablou cu n•m celule așezate pe n linii numerotate de la 1 la n și m coloane numerotate de la 1 la m.
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: 1 pentru o celulă ocupată de o clădire și 0 pentru o celulă neocupată.
Cerinţe
Cunoscând n, m și k, precum și tabloul care codifică imaginea, se cere să se determine:
1. Numărul S de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri C alese dintre celelalte k – 1 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 harta.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
Pe linia a doua se găsesc numerele naturale n, m și k separate prin câte un spațiu.
Pe fiecare dintre următoarele k linii, se găsesc câte patru numere naturale i1 j1 i2 j2
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 k clădiri.
Date de ieșire
- Dacă valoarea lui
peste1, atunci se va rezolva numai cerința1. În acest caz, în fişierul de ieşireharta.outse vor scrie cele două numereSșiCavând semnificația descrisă la cerința1, separate printr-un singur spațiu. - Dacă valoarea lui
peste2, atunci se va rezolva numai cerința2. În acest caz, fişierul de ieşireharta.outva conține tabloul care reprezintă harta obținută pe
baza imaginii din satelit. Fișierul va avean1linii. Pe fiecare linie se vor găsi câtem1valori0sau1separate prin câte un singur spațiu. Celulele situate pe marginile clădirilor vor avea valoarea1. Celulele din interiorul clădirilor, ca și cele din exterior, vor avea valoarea0.
Restricții și precizări
3 ≤ n, m ≤ 15001 ≤ i1 ≤ i2 ≤ n1 ≤ j1 ≤ j2 ≤ m1 ≤ k ≤ 10001 ≤ Lmax ≤ 50(Lmax– 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
harta.in
1 7 7 4 1 1 4 4 6 2 6 4 3 6 3 6 6 6 7 7
harta.out
16 2
Explicație
Clădirea de coordonate 1 1 4 4 este cel mai mare pătrat și ocupă S = 4•4 = 16 celule.
Clădirile de coordonate 3 6 3 6 și 6 6 7 7 “încap” în interiorul clădirii 1 1 4 4 fără să se suprapună peste celulele sale marginale. Deci C = 2.
Exemplul 2
harta.in
2 10 11 4 1 2 4 4 8 9 8 9 7 3 9 5 2 9 3 9
harta.out
0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
Explicație
În imagine sunt cinci drumuri determinate de dreptunghiurile: 1 1 10 1, 1 6 10 8, 1 10 10 11, 5 1 6 11 și 10 1 10 11.
Pe hartă, cele cinci drumuri vor avea coordonatele: 1 1 9 1, 1 6 9 6, 1 8 9 8, 5 1 5 8 și 9 1 9 8.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Harta:
/* 100 pucte
Constantin Galatan
*/
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define DIM 1501
typedef vector<int> VI;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct Dr {
int i1, j1, i2, j2;
Dr(int _i1, int _j1, int _i2, int _j2)
: i1(_i1), j1(_j1), i2(_i2), j2(_j2) {
}
};
vector<Dr> d;
int imax, jmax;
VI xa, ya, x, y, c1, c2, b1, b2;
int k, N, M, n, m, Lmax, L, H, T, nr_dr;
bool A[DIM][DIM], s1[DIM], s2[DIM];
void WriteMatr(bool a[][DIM], int N, int M);
int GetPos(VI, int val);
int main()
{
fin >> T >> N >> M >> k;
int i1, j1, i2, j2;
x.pb(0), y.pb(0); s1[0] = true; s2[0] = true;
for ( int i = 0; i < k; ++i )
{
fin >> i1 >> j1 >> i2 >> j2;
d.pb(Dr(i1, j1, i2, j2));
L = i2 - i1 + 1, H = j2 - j1 + 1;
if ( L == H && L > Lmax )
Lmax = L;
for ( int i = i1; i <= i2; ++i)
{
xa.pb(i), ya.pb(j1), xa.pb(i), ya.pb(j2);
if ( !s1[i] ) x.pb(i), s1[i] = true;
}
for ( int j = j1; j <= j2; ++j )
{
xa.pb(i1), ya.pb(j); xa.pb(i2), ya.pb(j);
if ( !s2[j] ) y.pb(j), s2[j] = true;
}
if ( !s1[i1 - 1] ) x.pb(i1 - 1), s1[i1 - 1] = true;
if ( !s2[j1 - 1] ) y.pb(j1 - 1), s2[j1 - 1] = true;
imax = max(imax, i2); jmax = max(jmax, j2);
}
if ( T == 1 )
{
for ( int i = 0; i < k; ++i )
{
L = d[i].i2 - d[i].i1 + 1, H = d[i].j2 - d[i].j1 + 1;
if ( L < Lmax - 1 && H < Lmax - 1 )
nr_dr++;
}
fout << Lmax * Lmax << ' ' << nr_dr << '\n';
}
else
{
c1 = VI(imax + 1);
c2 = VI(jmax + 1);
for (int i = 0; i < x.size(); ++i )
c1[x[i]]++;
for (int i = 0; i < y.size(); ++i )
c2[y[i]]++;
for (int i = 1; i <= imax; ++i )
c1[i] += c1[i - 1];
for (int i = 1; i <= jmax; ++i )
c2[i] += c2[i - 1];
b1 = VI(x.size()); // aici - x sortat
b2 = VI(y.size());
for ( int i = 0; i < x.size(); ++i )
b1[c1[x[i]] - 1] = x[i], c1[x[i]]--;
for ( int i = 0; i < y.size(); ++i )
b2[c2[y[i]] - 1] = y[i], c2[y[i]]--;
n = 0, m = 0; int i, j;
for (size_t k = 0; k < xa.size(); ++k )
{
i= GetPos(b1, xa[k]);
j = GetPos(b2, ya[k]);
n = max(n, i), m = max(m, j);
A[i][j] = 1;
}
if ( n < M ) n++;
if ( m < M ) m++;
WriteMatr(A, n, m);
}
fin.close();
fout.close();
return 0;
}
int GetPos(VI v, int val)
{
int i, p2, n = v.size();
int lo = 0, hi = n, mid;
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;
}
void WriteMatr(bool a[][DIM], int N, int M)
{
for ( int i = 1; i <= N; ++i )
{
for ( int j = 1; j <= M; ++j )
fout << a[i][j] << ' ';
fout << '\n';
}
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1103 Harta
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1103 Harta de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!