Cod sursa(job #604969)

Utilizator costyv87Vlad Costin costyv87 Data 26 iulie 2011 12:28:36
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>



FILE *f,*g;
//struct cp{int x,y;} v[50100];
int i,mx,my,dx,dy,n,a,b,xmn,ymn,xmni,ymni,x1,x2,y1,y2,con1,con2,d,d2,i2,i1;
int x[50100],y[50100];


int main() {
f=fopen("tribute.in","r");
g=fopen("tribute.out","w");

fscanf(f,"%d%d%d",&n,&dx,&dy);
mx=my=-1;

for (i=1;i<=n;i++) {
	fscanf(f,"%d%d",&a,&b);
	if (a>mx) mx=a;
	if (b>my) my=b;
	x[a]++;
	y[b]++;
	}

for (i1=0;x[i1]==0;i1++);
con1=0;
con2=0;
d=0; 
for (i2=50000;i2>i1+dx;i2--) { 
	if (!x[i2]) continue;
	d=d+(i2-i1-dx)*x[i2];
	con1+=x[i2];
	}

x1=i1;
x2=i1+dx;
xmn=d; xmni=0;

while (x2<=mx) {
	x2++;
	if (x[x2]) {
		con1-=x[x2];
		d-=x[x2];
		}
	if (x[x1]) {
		con2+=x[x1];
		}
	d+=con2;
	d-=con1;
	x1++;
	if (d<xmn) {
		xmn=d;
		xmni=x1;
		}
	}


for (i1=0;y[i1]==0;i1++);
con1=0;
con2=0;
d=0; 
for (i2=50000;i2>i1+dy;i2--) { 
	if (!y[i2]) continue;
	d=d+(i2-i1-dy)*y[i2];
	con1+=y[i2];
	}

y1=i1;
y2=i1+dy;
ymn=d;
ymni=0;

while (y2<=my) {
	y2++;
	if (y[y2]) {
		con1-=y[y2];
		d-=y[y2];
		}
	if (y[y1]) {
		con2+=y[y1];
		}
	d+=con2;
	d-=con1;
	y1++;
	if (d<ymn) {
		ymn=d;
		ymni=y1;
		}
	}

fprintf(g,"%d",xmn+ymn);

return 0;
fclose(g);
}