Primăria orașului Constanța reamenajează plaja din stațiunea Mamaia. Aceasta este reprezentată ca o zonă dreptunghiulară cu lățimea de a unități și lungimea de b unități. Pe plajă sunt trasate linii paralele cu laturile dreptunghiului astfel încât să formeze pătrate cu latura de o unitate, numite zone. Pe plajă se vor pune obiecte: umbrele și prosoape. Se consideră că dacă un obiect intră în interiorul unei zone, o ocupă în întregime. Se poziționează u umbrele de soare. Într-o zonă se poate așeza cel mult o umbrelă.

N turişti vin şi îşi aşează prosoapele pe plajă. Un prosop are formă dreptunghiulară şi va fi aşezat paralel cu laturile dreptunghiului. Turiştii îşi pot aşeza prosoapele pe zone libere sau peste prosoape deja aşezate. Un turist nu îşi poate aşeza însă prosopul pe plajă dacă suprafaţa acoperită de acesta include cel puţin o zonă în care se află o umbrelă.

M localnici au suprafeţe favorite pentru aşezarea prosoapelor. O suprafaţă favorită are forma unui dreptunghi cu laturile paralele cu laturile dreptunghiului care marchează plaja. După ce turiştii termină aşezarea prosoapelor, localnicii verifică dacă zonele din suprafaţa favorită sunt libere (neacoperite de prosoape aşezate de turişti sau de umbrele).

Cerința

Scrieţi un program care să determine numărul de turişti care au reuşit să îşi aşeze prosoapele pe plajă, precum și numărul de localnici ale căror zone favorite sunt libere.

Date de intrare

Fișierul de intrare plaja1.in conține pe prima linie trei numere naturale, separate prin câte un spațiu, a, b şi u, având semnificația din enunț. Fiecare din următoarele u linii conține o pereche de numere naturale x y, reprezentând o zonă în care se găsește o umbrelă. Următoarea linie din fișier conține un număr natural N, reprezentând numărul de turiști. Următoarele N linii descriu prosoapele turiștilor. Fiecare linie conține patru numere naturale x1 y1 x2 y2, ce reprezintă colțurile unui prosop. Linia următoare conține o singură valoare, M, reprezentând numărul de localnici. Pe următoarele M linii se află câte patru numere, separate prin câte un spațiu, x1’ y1’ x2’ y2’, ce reprezintă colțurile unei suprafețe favorite.

Date de ieșire

Fișierul de ieșire plaja1.out conţine pe prima linie două numere naturale separate printr-un spaţiu. Primul număr reprezintă numărul de turişti care şi-au aşezat prosoapele pe plajă, iar cel de-al doilea număr reprezintă numărul de localnici ale căror zone favorite sunt libere.

Restricții și precizări

Colţul din stânga sus al zonei dreptunghiulare are coordonatele (1,1)
3 ≤ a, b ≤ 2.000
0 ≤ u ≤ 100
3 ≤ m, n ≤ 100.000
Un prosop descris de (x1, y1, x2, y2) va avea 1 ≤ x1 ≤ x2 ≤ a şi 1 ≤ y1 ≤ y2 ≤ b
O suprafaţă favorită descrisă de (x1’, y1’, x2’, y2’) va avea 1 ≤ x1’ ≤ x2’ ≤ a şi 1 ≤ y1’ ≤ y2’ ≤ b

Exemplu

plaja1.in

plaja1.out

3 2

Explicație

Ultimul turist nu îşi poate aşeza prosopul. Zona favorită al celui de-al doilea localnic nu este liberă.

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 plaja1:

#include <cstdio>
#define NMax 2004

using namespace std;

int M, N, A, B, U, X[128], Y[128];
int S[NMax][NMax], Res;

int main()
{
    int i, j, x1, y1, x2, y2;
    bool ok = false;
    
    freopen("plaja1.in", "r", stdin);
    freopen("plaja1.out", "w", stdout);
    
    scanf("%d %d %d", &A, &B, &U);
    for (i = 1; i <= U; ++i)
        scanf("%d %d", &X[i], &Y[i]);
    scanf("%d", &N);
    for (i = 1; i <= N; ++i)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        
        for (j = 1, ok = true; j <= U && ok; ++j)
            if (x1 <= X[j] && X[j] <= x2 && y1 <= Y[j] && Y[j] <= y2)
                ok = false;
        if (!ok)
            continue;
        ++Res;
        ++S[x1][y1];
        ++S[x2+1][y2+1];
        --S[x1][y2+1];
        --S[x2+1][y1];
    }
    
    printf("%d ", Res);
    
    for (i = 1; i <= A; ++i)
        for (j = 1; j <= B; ++j)
            S[i][j] += S[i-1][j] + S[i][j-1] - S[i-1][j-1];
    
    for (i = 1; i <= U; ++i)
        S[X[i]][Y[i]] = 1;
        
    for (i = 1; i <= A; ++i)
        for (j = 1; j <= B; ++j)
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + (S[i][j] != 0);
        
    Res = 0;
    for (scanf("%d", &M); M; --M)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        Res += (S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1] == 0);
    }
    printf("%d\n", Res);
    
    return 0;
}

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 Adresa de email .

Rezolvarea problemei #2383 plaja1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2383 plaja1 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!

Rezolvare completă PbInfo #2383 plaja1