Cod sursa(job #25450)

Utilizator mastermageSchneider Stefan mastermage Data 4 martie 2007 12:38:20
Problema Ograzi Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.15 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define maxN 50100

int n,m,w,h,res;
struct po{
	int x,y;
};
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=en/2;
	while(st<en){
		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);
		if(cx>=og[r].x && cy>=og[r].y && cx<=og[r].x+w && cy<=og[r].y+h){
			res++;
		}else{
			if(r){
				r--;
				if(cx>=og[r].x && cy>=og[r].y && cx<=og[r].x+w && cy<=og[r].y+h){
					res++;
				}else{
					if(r<n-1){
						r++;
						if(cx>=og[r].x && cy>=og[r].y && cx<=og[r].x+w && cy<=og[r].y+h){
							res++;
						}
					}
				}
			}
		}
		
		
	}
	
	
	fprintf(fo,"%d",res);
	fclose(fi);fclose(fo);
	return 0;
}