Cod sursa(job #348719)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 16 septembrie 2009 17:36:22
Problema Tribute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct blorp{long x,y;}a[50005];
long n,x,y,x1,x2,y1,y2,nr,i,nrm,nry,xx1,xx2,yy1,yy2;
long cmpx(blorp x,blorp y)
{if(x.x<y.x)return 1;
return 0;}
long cmpy(blorp x,blorp y)
{if(x.y<y.y)return 1;
return 0;}
long distx(long x,long x1,long x2)
{if(x<x1)return x1-x;
if(x>x2)return x-x2;
return 0;}
long disty(long x,long x1,long x2)
{if(x<x1)return x1-x;
if(x>x2)return x-x2;
return 0;}
int main()
{
 freopen("tribute.in","r",stdin);   
 freopen("tribute.out","w",stdout);   
 scanf("%ld%ld%ld",&n,&x,&y);
 for(i=1;i<=n;++i)
    {scanf("%ld%ld",&a[i].x,&a[i].y);}
 sort(a+1,a+n,cmpx);
 x1=n/2-n%2;
 x2=n/2+1;
 while(a[x2].x-a[x1].x<x)
 {x2++;x1--;}
 if(a[x2-1].x-a[x1].x<=x)x1=a[x1].x,x2=x1+x;
 else x2=a[x2-1].x,x1=x2-x;
 xx1=x1;
 xx2=x2;
 nrm=2000000000;
 while(nr<=nrm)
  {nr=0;
   for(i=1;i<=n;++i)
      nr+=distx(a[i].x,x1,x2);
   if(nr<nrm)nrm=nr;
   ++x1;++x2;}
 while(nr<=nrm)
  {nr=0;
   for(i=1;i<=n;++i)
      nr+=distx(a[i].x,xx1,xx2);
   if(nr<nrm)nrm=nr;
   --xx1;--xx2;}
 sort(a+1,a+n,cmpy);
 y1=n/2-n%2;
 y2=n/2+1;
 while(a[y2].y-a[y1].y<y)
 {y2++;y1--;}
 if(a[y2-1].y-a[y1].y<=y)y1=a[y1].y,y2=y1+y;
 else y2=a[y2-1].y,y1=y2-y;
 yy1=y1;
 yy2=y2;
 nry=2000000000;
 while(nr<=nry)
  {nr=0;
   for(i=1;i<=n;++i)
      nr+=disty(a[i].y,y1,y2);
   if(nr<nry)nry=nr;
   ++y1;++y2;}   
 while(nr<=nry)
  {nr=0;
   for(i=1;i<=n;++i)
      nr+=disty(a[i].y,yy1,yy2);
   if(nr<nry)nry=nr;
   --yy1;--yy2;}   
 printf("%ld\n",nrm+nry);
 return 0;   
}