Prietenul nostru, Pit, se află în Grecia antică, în cea mai vestită piață publică. Considerăm că piața este un dreptunghi din plan, de dimensiuni X și Y. Dacă reprezentăm piața într-un reper cartezian xOy, aceasta are cele patru vârfuri în punctele de coordonate (0,0), (X,0), (X,Y) și (0,Y). În fiecare punct (a,b), cu a ∈ {1,...,X} și b ∈ {1,...,Y}, se află câte o tarabă care vinde echere. Prietenul nostru este afacerist și vrea să închirieze o parcelă de teren dreptunghiulară, având laturile paralele cu laturile pieței, iar cele patru vârfuri de coordonate numere naturale. Vârfurile parcelei se află în interiorul pieței sau pe laturile acesteia. În această parcelă, Pit vrea să cuprindă cât mai multe tarabe speciale, care au următoarele proprietăți:

distanta de la origine la tarabă este număr natural;
nu există nici o altă tarabă pe segmentul dintre origine și tarabă.

Cerința

Cunoscându-se valorile X, Y și coordonatele (SX_i, SY_i) și (DX_i, DY_i) pentru Q parcele, unde 1 ≤ i ≤ Q, să se afle, pentru fiecare parcelă, care este numărul de tarabe speciale pe care le conține.

Date de intrare

Fișierul de intrare agora.in conține pe prima linie trei numere naturale despărțite prin câte un spațiu, X, Y și Q, cu semnificația din enunț. Pe următoarele Q rânduri se află câte patru numere naturale nenule Sx_i, Sy_i, Dx_i, Dy_i, separate prin câte un spațiu, cu semnificația din enunț.

Date de ieșire

Pe fiecare dintre primele Q rânduri ale fișierului agora.out se va afla câte un număr natural, numărul de pe linia
i reprezentând numărul tarabelor speciale conținute de către parcela i.

Restricții și precizări

2 ≤ X ≤ 7000
2 ≤ Y ≤ 7000
1 ≤ Q ≤ 100 000
o tarabă face parte dintr-o parcelă și dacă se află pe laturile ei;
(SX_i, SY_i) și (DX_i, DY_i) nu se vor afla în afara dreptunghiului asociat pieței, dar se pot afla pe laturile lui;
Pentru teste în valoare de 10 puncte: X, Y ≤ 100 și Q ≤ 100
Pentru alte teste în valoare de 20 puncte: X, Y ≤ 2000 și Q ≤ 1000
Pentru alte teste în valoare de 10 puncte: X, Y ≤ 2000 și Q ≤ 100 000

Exemplu

agora.in

5 5 2
1 5 3 4
3 4 4 3

agora.out

1
2

Explicație

Prima parcelă conține taraba specială de la punctul (3, 4). A doua parcelă conține tarabele speciale (3,4) și (4,3).

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

/**
Solutie cu generare folosind inmultire de matrici
*/
#include <iostream>
#include <fstream>
#include <queue>
#include <iterator>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define x first
#define y second.first
#define z second.second
#define make_triple(a, b, c) make_pair(a, make_pair(b, c))

ifstream fin("agora.in");
ofstream fout("agora.out");

int x_1, y_1, x_0, y_0, ans;
int X, Y, K, i, j, xMax, yMax;
int mat[2500][2500];

vector<int> difX, difY;
vector<pair<int, int> > points;
queue<pair<int, pair<int, int> > > Q;
pair<int, pair<int, int> > crt, nxt;

bool isBounded(int a, int b) {
    if (abs(a) > X || abs(b) > Y)
        return false;
    return true;
}

int main()
{
    fin >> X >> Y >> K; /// Plane is 0 to X,Y
    Q.push(make_triple(3, 4, 5));

    while(!Q.empty()) {
        crt = Q.front(); Q.pop();

        if (crt.x <= X && crt.y <= Y) {
            points.push_back(make_pair(crt.x, crt.y));
            difX.push_back(crt.x);
            difY.push_back(crt.y);
        }

        if (crt.y <= X && crt.x <= Y) {
            points.push_back(make_pair(crt.y, crt.x));
            difX.push_back(crt.y);
            difY.push_back(crt.x);
        }

        nxt.x = -crt.x + 2 * crt.y + 2 * crt.z;
        nxt.y = -2 * crt.x + crt.y + 2 * crt.z;
        nxt.z = -2 * crt.x + 2 * crt.y + 3 * crt.z;
        if (isBounded(nxt.x, nxt.y)) {
            Q.push(nxt);
        }

        nxt.x = crt.x + 2 * crt.y + 2 * crt.z;
        nxt.y = 2 * crt.x + crt.y + 2 * crt.z;
        nxt.z = 2 * crt.x + 2 * crt.y + 3 * crt.z;
        if (isBounded(nxt.x, nxt.y)) {
            Q.push(nxt);
        }

        nxt.x = crt.x + -2 * crt.y + 2 * crt.z;
        nxt.y = 2 * crt.x + -crt.y + 2 * crt.z;
        nxt.z = 2 * crt.x + -2 * crt.y + 3 * crt.z;
        if (isBounded(nxt.x, nxt.y)) {
            Q.push(nxt);
        }
    }

    sort(difX.begin(), difX.end());
    sort(difY.begin(), difY.end());
    unique(difX.begin(), difX.end());
    unique(difY.begin(), difY.end());

    for(i = 0 ; i < points.size() ; i++) {
        mat[distance(difY.begin(), lower_bound(difY.begin(), difY.end(), points[i].second)) + 1][distance(difX.begin(), lower_bound(difX.begin(), difX.end(), points[i].first)) + 1] = 1;
    }

    xMax = difX.size();
    yMax = difY.size();

    for (i = 1 ; i <= xMax + 1 ; i++) {
        for (j = 1 ; j <= yMax + 1 ; j++) {
                mat[i][j] += mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];
        }
    }

    for (i = 0 ; i < K ; i++) {
        fin >> x_1 >> y_1 >> x_0 >> y_0;
        x_1 = distance(difX.begin(), lower_bound(difX.begin(), difX.end(), x_1)) + 1;
        x_0 = distance(difX.begin(), upper_bound(difX.begin(), difX.end(), x_0));
        y_1 = distance(difY.begin(), upper_bound(difY.begin(), difY.end(), y_1));
        y_0 = distance(difY.begin(), lower_bound(difY.begin(), difY.end(), y_0)) + 1;

        ans = mat[x_0][y_1] - mat[x_0][y_0 - 1] - mat[x_1-1][y_1] + mat[x_1-1][y_0-1];
        fout << ans << '\n';
    }

    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 #2465 agora

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