Cod sursa(job #2900694)

Utilizator vladdobro07vladdd vladdobro07 Data 11 mai 2022 22:45:51
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("ograzi.in");
ofstream cout("ograzi.out");
const int nmax=50000;
int n,m,w,h,x,y,maxx=0,sol=0;
pair<int,int>v[nmax+3],v1[nmax+3];
int binxl(int st,int dr,int x) {
        st=max(st,0);
        dr=min(dr,n);
        int mid,last=-1;
        while(st<=dr) {
                mid=(st+dr)/2;
                if(v[mid].first>=x) {
                        last=mid;
                        dr=mid-1;
                } else if(v[mid].first<x)
                                st=mid+1;
        }
        return last;
}
int binyl(int st,int dr,int x) {
        st=max(st,0);
        dr=min(dr,n);
        int mid,last=-1;
        while(st<=dr) {
                mid=(st+dr)/2;
                if(v1[mid].first>=x) {
                        last=mid;
                        dr=mid-1;
                } else if(v1[mid].first<x)
                                st=mid+1;
        }
        return last;
}
void query(int x,int y) {
        int lx=binxl(0,n,x-w+1),ly=binyl(0,n,y-h+1);
        if(v[lx].first<=x&&v[lx].first+w>=x&&v[lx].second<=y&&v[lx].second+h>=y){
                sol++;
                return;
        }
        if(v1[ly].first<=y&&v1[ly].first+h>=y&&v1[ly].second<=x&&v1[ly].second+w>=x)
                sol++;
}
int main() {
        cin>>n>>m>>h>>w;
        for(int i=1; i<=n; i++) {
                cin>>v[i].second>>v[i].first;
                v1[i].first=v[i].second;
                v1[i].second=v[i].first;
                maxx=max(maxx,max(v[i].first,v[i].second));
        }
        sort(v+1,v+n+1);
        sort(v1+1,v1+n+1);
        //for(int i=1; i<=n; i++)
                //cerr<<v[i].first<<" "<<v[i].second<<", "<<v1[i].first<<" "<<v1[i].second<<'\n';
        for(int i=1; i<=m; i++) {
                cin>>y>>x;
                query(x,y);
        }
        cout<<sol;
        return 0;
}