Cod sursa(job #2490839)

Utilizator altcontnoualt cont altcontnou Data 11 noiembrie 2019 08:31:12
Problema Ograzi Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, m, latime, inaltime, y1, y2, x1, x2;
pair<int,int>ograzi[50005];
pair<int,int>oi[100005];

bool cautare(pair<int,int>a)
{
    int st=1, dr=n, mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        x1=ograzi[mij].first;
        x2=x1+latime;
        y1=ograzi[mij].second;
        y2=y1+inaltime;
        if (a.first<=x2 && a.first>=x1 && a.second<=y2 && a.second>=y1)
        {
            return true;
        }
        if (a.first<x1 || a.first<=x2 && a.first>=x1 && a.second<y1)
            dr=mij-1;
        else
            st=mij+1;
    }
    return false;
}

void solve()
{
    int rez=0;
    for (int i=1; i<=m; ++i)
    {
        if (cautare(oi[i]))
            rez++;
    }
    printf("%d",rez);
}

int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    scanf("%d %d %d %d",&n,&m,&latime,&inaltime);
    for (int i=1; i<=n; ++i)
    {
        scanf("%d %d",&ograzi[i].first,&ograzi[i].second);
    }
    for (int i=1; i<=m; ++i)
    {
        scanf("%d %d",&oi[i].first,&oi[i].second);
    }
    sort(ograzi+1,ograzi+n+1);
    solve();
    return 0;
}