Cod sursa(job #536824)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 19 februarie 2011 15:12:04
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define DIM 50005

int x[DIM],y[DIM];
int n,dx,dy,i;

int solve (int v[DIM],int dv)
{
    int st,dr,a,b,d,i,j,dmin;

    for (a=v[0], b=v[0]+dv, i=1; v[i]<b; ++i);
	for (d=0, j=i; j<n; ++j)
        d+=v[j]-b;
	dmin=d;
	for (st=1, dr=i; dr<n; )
	{
        if (v[st]-a<v[dr]-b)
        {
            d+=st*(v[st]-a)-(n-dr)*(v[st]-a);
            a=v[st++];
            b=a+dv;
        }
        else
        {
            d+=st*(v[dr]-b)-(n-dr)*(v[dr]-b);
            b=v[dr++];
            a=b-dv;
        }
        if (d<dmin)
            dmin=d;
	}

	return dmin;
}

int main ()
{
    freopen ("tribute.in","r",stdin);
    freopen ("tribute.out","w",stdout);
    scanf ("%d%d%d",&n,&dx,&dy);
    for (i=0; i<n; ++i)
        scanf ("%d%d",&x[i],&y[i]);
    sort (x,x+n); x[n]=INF;
    sort (y,y+n); y[n]=INF;
    printf ("%d",solve (x,dx)+solve (y,dy));

    return 0;
}