Cod sursa(job #41493)

Utilizator mastermageSchneider Stefan mastermage Data 28 martie 2007 12:12:10
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 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){return a.x>b.x;}

int bsch(int cx){
	int st=0,en=n-1,c;
	while(st<en){
		c=(st+en)>>1;
		if(cx<og[c].x) st=c+1; else en=c;
	}
	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);
		
		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;
}