Cod sursa(job #2496155)

Utilizator ialexia_ioanaAlexia Ichim ialexia_ioana Data 20 noiembrie 2019 12:05:30
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda casiaiziscanudaisimulareprimaora Marime 1.72 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int NMAX=100005;
int n, m;
int limst, limdr;
struct coord
{
    int x, y, ord;
};
coord v[NMAX];
bool cmp(coord a, coord b)
{
    if(a.x>b.x)
        return 0;
    return 1;
}
void search_bin(int a, coord v[], int i)
{
    int st, dr, mid;
    st=1;
    dr=n;
    mid=(st+dr)/2;
    while(st<=dr && a!=v[mid].x)
    {
        if(a<v[mid].x)
            dr=mid-1;
        if(a>=v[mid].x)
            st=mid+1;
        mid=(st+dr)/2;
    }
    if(a==v[mid].x)
        st=mid;
    limdr=v[min(st, dr)].ord;
    a-=i;
    st=1;
    dr=n;
    mid=(st+dr)/2;
    while(st<=dr && a!=v[mid].x)
    {
        if(a<=v[mid].x)
            dr=mid-1;
        if(a>v[mid].x)
            st=mid+1;
        mid=(st+dr)/2;
    }
    if(a==v[mid].x)
        st=mid;
    limst=v[min(st, dr)].ord;
    //printf("%d %d\n", limst, limdr);
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    int w, h, i, x, y, a, b, c, d, cnt=0;
    scanf("%d%d%d%d", &n, &m, &w, &h);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &v[i].x, &v[i].y);
        v[i].ord=i;
    }
    sort(v+1, v+n+1, cmp);
    //for(i=1; i<=n; i++)
        //printf("%d %d\n", v[i].x, v[i].y);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &x, &y);
        search_bin(x, v, w);
        a=min(limdr, limst);
        b=max(limdr, limst);
        for(int j=a; j<=b; j++)
        {
            if(v[j].x<=x && x<=v[j].x+w && v[j].y<=y && y<=v[j].y+h)
            {
                cnt++;
                break;
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}