Cod sursa(job #122094)

Utilizator CezarMocanCezar Mocan CezarMocan Data 10 ianuarie 2008 20:27:15
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct dulap
    { long x; long y;};

long n,i,j,x[50010],y[50010],dx,dy,u,d,m;
dulap v[50010];

bool cmp1(dulap a, dulap b)
    {
    if (a.x<=b.x)
        return true;
    else
        return false;   
    }

bool cmp2(dulap a, dulap b)
    {
    if (a.y<=b.y)
        return true;
    else
        return false;   
    }

int main(){
freopen("tribute.in","r",stdin);
freopen("tribute.out","w",stdout);
scanf("%d%d%d",&n,&dx,&dy);
for (i=1;i<=n;i++)
    scanf("%d%d",&v[i].x,&v[i].y);    
sort(v+1,v+n+1,cmp1);
//line sweeping pe orizontala
//prima data fac pentru linia 0 si vad ce distanta da
//la urmatoarele actualizez in O(1) in functie de cate se apropie si cate se departeaza
for (i=1;i<=n;i++)
    if (v[i].x>dx)
        {
        x[0]+=(v[i].x-dx);
        if (u==0)
            u=i;
        }
d=1;
u--;
for (i=1;i<=50000;i++)
    {
    while ((v[d].x<i)&&(d<=n))  
        d++;
    x[i]=x[i-1]+(d-1)-(n-u+1);
    while ((v[u].x<=i+dx)&&(u<=n))
        u++;
    }
u=0;
sort(v+1,v+n+1,cmp2);
for (i=1;i<=n;i++)
    if (v[i].y>dy)
        {
        y[0]+=(v[i].y-dy);
        if (u==0)
            u=i;
        }
d=1;
u--;
for (i=1;i<=50000;i++)
    {
    while ((v[d].y<i)&&(d<=n))
        d++;
    y[i]=y[i-1]+(d-1)-(n-u+1);
    while ((v[u].y<=i+dy)&&(u<=n))
        u++;
    }
/*for (i=0;i<=5;i++)
    printf("%d %d \n",x[i],y[i]);*/
m=x[0]+y[0];
for (i=1;i<=50000;i++)
    if (x[i]+y[i]<m)
        m=x[i]+y[i];
printf("%ld",m);
return 0;
}