Cod sursa(job #2837012)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 21 ianuarie 2022 15:02:01
Problema Ograzi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>

using namespace std;

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

const int inf = 0x3f3f3f3f;
int n, m, lung, lat, ans;

struct coords{
    int x, y;
}v[50005], bee[100005];

multiset <int> curte;
multiset <int> :: iterator it;
string s;

void citire()
{
    getline(fin, s);
    s = s + ' ';
    int ind = 0, semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    n = semn * nr;
    ind++;
    semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    m = semn * nr;
    ind++;
    semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    lung = semn * nr;
    ind++;
    semn = 1, nr = 0;
    if(s[ind] == '-')
    {
        semn = -1;
        ind++;
    }
    while(s[ind] != ' ')
    {
        nr = nr * 10 + (s[ind] - '0');
        ind++;
    }
    lat = semn * nr;
    for(int i = 1; i <= n; i++)
    {
        getline(fin, s);
        s = s + ' ';
        int ind = 0, semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        v[i].x = semn * nr;
        ind++;
        semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        v[i].y = semn * nr;
    }
    for(int i = 1; i <= m; i++)
    {
        getline(fin, s);
        s = s + ' ';
        int ind = 0, semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        bee[i].x = semn * nr;
        ind++;
        semn = 1, nr = 0;
        if(s[ind] == '-')
        {
            semn = -1;
            ind++;
        }
        while(s[ind] != ' ')
        {
            nr = nr * 10 + (s[ind] - '0');
            ind++;
        }
        bee[i].y = semn * nr;
    }
}

bool cmp(coords a, coords b)
{
    if(a.y == b.y)
        return a.x <= b.x;
    return a.y < b.y;
}

int main()
{
    citire();
    sort(v + 1, v + n + 1, cmp);
    sort(bee + 1, bee + m + 1, cmp);
    v[n + 1] = {inf, inf};
    bee[m + 1] = {inf, inf};
    int st = 1, dr = 1, b = 1;
    while(b <= m)
    {
        int rez = cmp(v[dr], bee[b]);
        coords a;
        if(rez == 1)
            a = v[dr];
        else
            a = bee[b];
        while(a.y - v[st].y > lat)
        {
            it = curte.lower_bound(v[st].x);
            curte.erase(it);
            st++;
        }
        if(rez == 1)
            curte.insert(v[dr].x), dr++;
        else
        {
            if(!curte.empty())
            {
                if(*curte.begin() > a.x);
                else
                {
                    it = curte.upper_bound(a.x);
                    it--;
                    if(a.x - *it <= lung)
                        ans++;
                }
            }
            b++;
        }
    }
    fout << ans;
    return 0;
}