Cod sursa(job #354368)

Utilizator Addy.Adrian Draghici Addy. Data 7 octombrie 2009 20:31:11
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#define DIM 50002
#define INF 2000000000

int Sx1[DIM], Sx2[DIM], Sy1[DIM], Sy2[DIM], vizx[DIM], vizy[DIM];
int n, i, dx, dy, x, y, xMAX, yMAX, p, SxC, SyC;
long long MINx, MINy;

int main() {
	
	FILE *f = fopen("tribute.in", "r");
	FILE *g = fopen("tribute.out", "w");
	
	fscanf(f, "%d %d %d", &n, &dx, &dy);
	
	for (i = 1; i <= n; i++) {
		fscanf(f, "%d %d", &x, &y);
		vizx[x]++, vizy[y]++;
		if (x > xMAX)
			xMAX = x;
		if (y > yMAX)
			yMAX = y;
	}
	
	if (vizx[0]) p = vizx[0];
	for (i = 1; i <= xMAX; i++) {
		Sx1[i] = Sx1[i-1] + p;
		if (vizx[i])
			p += vizx[i];
	}
	
	p = 0;
	for (i = xMAX; i >= 0; i--) {
		Sx2[i] = Sx2[i+1] + p;
		if (vizx[i])
			p += vizx[i];
	}
	
	if (vizy[0]) p = vizy[0];
	for (i = 1; i <= yMAX; i++) {
		Sy1[i] = Sy1[i-1] + p;
		if (vizy[i])
			p += vizy[i];
	}
	
	p = 0;
	for (i = yMAX; i >= 0; i--) {
		Sy2[i] = Sy2[i+1] + p;
		if (vizy[i])
			p += vizy[i];
	}
	
	MINx = INF;
	MINy = INF;
	
	for (i = 0; i <= xMAX-dx; i++) {
		SxC = Sx1[i] + Sx2[i+dx];
		if (SxC < MINx)
			MINx = SxC;
	}
	
	for (i = 0; i <= yMAX-dy; i++) {
		SyC = Sy1[i] + Sy2[i+dy];
		if (SyC < MINy)
			MINy = SyC;
	}
	
	fprintf(g, "%lld", MINx + MINy);
	
	fclose(f);
	fclose(g);
	
	return 0;
}