Cod sursa(job #76617)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 10 august 2007 17:04:47
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<stdio.h>
long long n,dx,yx,x[50002],y[50002],marquee[50001],cat[50001],xdrp,aux,i,best,j,ydrp,dst;
long long modul(long long val)
 {
  if (val<0) return -val;
  return val;
 }
int main()
{
  freopen("tribute.in","r",stdin);
  freopen("tribute.out","w",stdout);
  scanf("%ld %ld %ld",&n,&dx,&yx);
  for(i=1;i<=n;i++)
   scanf("%ld %ld",&x[i],&y[i]);
  for(i=1;i<=n;i++)
   marquee[x[i]]++;
  cat[0]=marquee[0];
  for(i=1;i<=50000;i++)
    cat[i]=cat[i-1]+marquee[i];
    best=2000000;
  for(i=0;i<=50000;i++)
   {
     if (best>modul(cat[i]-n+cat[i+dx-1]))
                  {
                  best=modul(cat[i]-n+cat[i+dx-1]);
                  xdrp=i;
                  aux=cat[i-1]+n-cat[i+dx];
                  }
                 else
     if (best==modul(cat[i]-n+cat[i+dx-1])&&(aux>cat[i-1]+n-cat[i+dx]))
                {
                  aux=cat[i-1]+n-cat[i+dx];
                  xdrp=i;
                }
   }
  for(i=0;i<=50000;i++)
   marquee[i]=0;
  for(i=1;i<=n;i++)
   marquee[y[i]]++;
    cat[0]=marquee[0];
  for(i=1;i<=50000;i++)
    cat[i]=cat[i-1]+marquee[i];
    best=2000000;
  for(i=0;i<=50000;i++)
   {
     if (best>modul(cat[i]-n+cat[i+dx-1]))
                  {
                  best=modul(cat[i]-n+cat[i+dx-1]);
                  ydrp=i;
                  aux=cat[i-1]+n-cat[i+dx];
                  }
                 else
     if (best==modul(cat[i]-n+cat[i+dx-1])&&(aux>cat[i-1]+n-cat[i+dx]))
                {
                  aux=cat[i-1]+n-cat[i+dx];
                  ydrp=i;
                }
   }
  for(i=1;i<=n;i++)
   {
   if (x[i]<=xdrp+dx&&x[i]>=xdrp) dst+=0;
   else
    if (modul(x[i]-xdrp)>modul(x[i]-xdrp-dx)) dst+=modul(x[i]-xdrp-dx);
                                   else dst+=modul(x[i]-xdrp);
   }
  for(i=1;i<=n;i++)
   {
   if (y[i]<=ydrp+yx&&y[i]>=ydrp) dst+=0;
          else
    if (modul(y[i]-ydrp)>modul(y[i]-ydrp-yx)) dst+=modul(y[i]-ydrp-yx);
                                   else dst+=modul(y[i]-ydrp);
   }
  printf("%lld",dst);
  printf("\n");
  fclose(stdout);
  return 0;
}