Cod sursa(job #41334)

Utilizator mastermageSchneider Stefan mastermage Data 28 martie 2007 10:27:41
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define maxN 50100

struct po{int x,y;};

int n,m,w,h,res;
po og[maxN];

bool pred(po a,po b){
	if(a.x<b.x || (a.x==b.x && a.y<=b.y))return true;
	return false;
}

int bsch(int cx,int cy){
	int st=0,en=n-1,c;
	while(st<en){
		c=(st+en)>>1;
		if(cx<og[c].x || (cx==og[c].x && cy<=og[c].y )){
			en=c-1;
		}else{
			st=c+1;
		}
	}
	return st;
}

int main(){
	FILE*fi=fopen("ograzi.in","r"),*fo=fopen("ograzi.out","w");
	fscanf(fi,"%d %d %d %d",&n,&m,&w,&h);
	for(int i=0;i<n;i++)fscanf(fi,"%d %d",&og[i].x,&og[i].y);
	
	sort(og,og+n,pred);
	
	for(int i=0;i<m;i++){
		int cx,cy;fscanf(fi,"%d %d",&cx,&cy);
		int r=bsch(cx,cy),cr=r;
		
		while(r>=0){
			
			if(cx>=og[r].x && cx<=og[r].x+w){
				if(cy>=og[r].y && cy<=og[r].y+h){res++;break;cr=n;}
			}else break;
			r--;
		}
		r=cr;
		while(r<n){
			
			if(cx>=og[r].x && cx<=og[r].x+w){
				if(cy>=og[r].y && cy<=og[r].y+h){res++;break;}
			}else break;
			r++;
		}
		
	}
	
	
	fprintf(fo,"%d",res);fclose(fi);fclose(fo);return 0;
}