Cod sursa(job #473447)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 29 iulie 2010 15:11:05
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define N 50001
#define MAX 50000
#define INF 0x7fffffff
int x[N],y[N];
int s1[N],s2[N];
int comp(const void* a,const void *b)
{return *(int*)a-*(int*)b;
}

int main ()
{int n,dx,dy,p,c,mp,t,r,i,min;
 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",&x[i],&y[i]);

 qsort(x,n+1,sizeof(int),comp);
 qsort(y,n+1,sizeof(int),comp);
 
 for (p=0,mp=1,c=0;p<=MAX;p++)
 {if(p>0)s1[p]=s1[p-1]+c;
  while(x[mp]==p&&mp<=MAX)
  {c++;
   mp++;
  }
 }
 
 for (p=50000,mp=n,c=0;p>=0;p--)
 {if(p<MAX)s2[p]=s2[p+1]+c;
  while(x[mp]==p&&mp>=1)
  {c++;
   mp--;
  }
 }
 
 for (i=0,min=INF;i+dx<=MAX;i++)
 {if(min>s1[i]+s2[i+dx])
  {min=s1[i]+s2[i+dx];
  }
 }
 r=min;
 memset(s1,0,sizeof(s1));
 memset(s2,0,sizeof(s2));
 //
 for (p=0,mp=1,c=0;p<=MAX;p++)
 {if(p>0)s1[p]=s1[p-1]+c;
  while(y[mp]==p&&mp<=MAX)
  {c++;
   mp++;
  }
 }
 
 for (p=50000,mp=n,c=0;p>=0;p--)
 {if(p<MAX)s2[p]=s2[p+1]+c;
  while(y[mp]==p&&mp>=1)
  {c++;
   mp--;
  }
 }
 
 for (i=0,min=INF;i+dy<=MAX;i++)
 {if(min>s1[i]+s2[i+dy])
  {min=s1[i]+s2[i+dy];
  }
 }
 //
 r+=min;
 printf("%d",r);
 return 0;
}