Cod sursa(job #25889)

Utilizator TheCreeepIonita Andrei Lucian TheCreeep Data 4 martie 2007 15:54:37
Problema Ograzi Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <stdio.h>
#include <stdlib.h>
int ogrx[50001],ogry[50001],sheepx[100001],sheepy[100001];
int w,h,n,m;
struct {
	int x,y,startx,stopx,starty,stopy;
} ogr[50001];
struct {
	int x,y,last,next,used;
} oaie[100001];
int answer;
void cit()
{
	int i,t,j;
	char buf[100];
	FILE *f=fopen("ograzi.in","r");
	fscanf(f,"%d %d %d %d\n",&n,&m,&w,&h);
	for(j=1;j<=n;j++)
		{
			fgets(buf, 100, f);
			t=0;
			for(i=0;buf[i]!=' ';i++) t=t*10+buf[i]-'0';
			ogr[j].x=t;
			t=0;
			for(i++;buf[i]!='\n';i++) t=t*10+buf[i]-'0';
			ogr[j].y=t;
		}
	for(j=1;j<=m;j++)
		{
			fgets(buf, 100, f);
			t=0;
			for(i=0;buf[i]!=' ';i++) t=t*10+buf[i]-'0';
			oaie[j].x=t;
			t=0;
			for(i++;buf[i]!='\n';i++) t=t*10+buf[i]-'0';
			oaie[j].y=t;
		}
	fclose(f);
}
static int cmpogrx(const void * a, const void *b){	int * aa = (int*) a;	int * bb = (int*) b;	return ogr[*aa].x-ogr[*bb].x;}
static int cmpogry(const void * a, const void *b){	int * aa = (int*) a;	int * bb = (int*) b;	return ogr[*aa].y-ogr[*bb].y;}
static int cmpsheepx(const void * a, const void *b){	int * aa = (int*) a;	int * bb = (int*) b;	return oaie[*aa].x-oaie[*bb].x;}
static int cmpsheepy(const void * a, const void *b){	int * aa = (int*) a;	int * bb = (int*) b;	return oaie[*aa].y-oaie[*bb].y;}
void rez()
{
	int i,j,k,t;
	for(i=1;i<=n;i++) {ogrx[i]=i;ogry[i]=i;}
	for(i=1;i<=m;i++) {sheepx[i]=i;sheepy[i]=i;}
	ogr[0].x=-1;
	ogr[0].y=-1;
	oaie[0].x=-1;
	oaie[0].y=-1;
	qsort(ogrx+1, n, sizeof(ogrx[0]),cmpogrx);
	qsort(sheepx+1, n, sizeof(sheepx[0]),cmpsheepx);
	j=1;
	k=1;
	for(i=1;i<=m;i++) // i -oaie, j -ogradastart, k -ogradastop
	{
		while (oaie[sheepx[i-1]].x < ogr[ogrx[j]].x && oaie[sheepx[i]].x >= ogr[ogrx[j]].x && j<=n)
		{
			ogr[ogrx[j]].startx = i;
			j++;
		}
		while (oaie[sheepx[i-1]].x <= ogr[ogrx[k]].x+w && oaie[sheepx[i]].x > ogr[ogrx[k]].x+w && k<=n)
		{
			ogr[ogrx[k]].stopx = i-1;
			k++;
		}		
	}
	for(i=1;i<=n;i++) if (ogr[i].startx!=0 && ogr[i].stopx==0)  ogr[i].stopx=m;
	qsort(ogry+1, n, sizeof(ogry[0]),cmpogry);
	qsort(sheepy+1, n, sizeof(sheepy[0]),cmpsheepy);
	j=1;
	k=1;
	for(i=1;i<=m;i++) // i -oaie, j -ogradastart, k -ogradastop
	{
		while (oaie[sheepy[i-1]].y < ogr[ogry[j]].y && oaie[sheepy[i]].y >= ogr[ogry[j]].y && j<=n)
		{
			ogr[ogry[j]].starty = i;
			j++;
		}
		while (oaie[sheepy[i-1]].y <= ogr[ogry[k]].y+h && oaie[sheepy[i]].y > ogr[ogry[k]].y+h && k<=n)
		{
			ogr[ogry[k]].stopy = i-1;
			k++;
		}		
	}
	for(i=1;i<=n;i++) if (ogr[i].starty!=0 && ogr[i].stopy==0)  ogr[i].stopy=m;

	for(i=1;i<=n;i++)
	if (ogr[i].stopx-ogr[i].startx < ogr[i].stopy - ogr[i].starty)
	{
		for(j=ogr[i].startx; j<=ogr[i].stopx; j++)
		{
			t=sheepx[j];
			if (!oaie[t].used && oaie[t].y >= ogr[i].y && oaie[t].y<=ogr[i].y+h)
			{
				oaie[t].used=1;
				answer++;
			}
		}
		
	}
	else
	{
		for(j=ogr[i].starty; j<=ogr[i].stopy; j++)
		{
			t=sheepy[j];
			if (!oaie[t].used && oaie[t].x >= ogr[i].x && oaie[t].x<=ogr[i].x+w)
			{
				oaie[t].used=1;		
				answer++;
			}
		}		
	}
	
}
void scr()
{
	FILE *f=fopen("ograzi.out","w");
	fprintf(f,"%d\n",answer);
	fclose(f);
}
int main (void)
{
	cit();
	rez();
	scr();
	return 0;
}