Cod sursa(job #122115)

Utilizator CezarMocanCezar Mocan CezarMocan Data 10 ianuarie 2008 20:45:15
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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,cmp2);
//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].y>dx)
        {
        x[0]+=(v[i].y-dx);
        if (u==0)
            u=i;
        }
d=1;
//u--;
for (i=1;i<=50000;i++)
    {
    while ((v[d].y<i)&&(d<=n))  
        d++;
//    printf("%d %d \n",d,u);
    x[i]=x[i-1]+(d-1)-(n-u+1);
    while ((v[u].y<=i+dx)&&(u<=n))
        u++;
    }
u=0;
sort(v+1,v+n+1,cmp1);
for (i=1;i<=n;i++)
    if (v[i].x>dy)
        {
        y[0]+=(v[i].x-dy);
        if (u==0)
            u=i;
        }
d=1;
//u--;
for (i=1;i<=50000;i++)
    {
    while ((v[d].x<i)&&(d<=n))
        d++;
    y[i]=y[i-1]+(d-1)-(n-u+1);
    while ((v[u].x<=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];*/
sort(x+1,x+50001);
sort(y+1,y+50001);
printf("%ld",x[1]+y[1]);
return 0;
}