Pagini recente » Cod sursa (job #1718735) | Cod sursa (job #73657)
Cod sursa(job #73657)
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define fin "tribute.in"
#define fout "tribute.out"
#define Nmax 50001
#define MAX 1<<30
#define DBGg
#define FL
struct dot { int x,y; };
vector <dot> v;
int N,dx,dy,a[Nmax],b[Nmax];
int x1,y1,x2,y2;
int ret;
bool cmpx(dot a,dot b)
{
return a.x < b.x;
}
bool cmpy(dot a,dot b)
{
return a.y < b.y;
}
int main()
{
int i,j,bst;
dot aux;
freopen(fin,"r",stdin);
#ifdef FL
freopen(fout,"w",stdout);
#endif
scanf("%d%d%d",&N,&dx,&dy);
for (i=0;i<N;++i)
{
scanf("%d%d",&aux.x,&aux.y);
v.push_back(aux);
}
//baleiez pe OX
sort(v.begin(),v.end(),cmpx);
for (i=1;i<N;++i)
{
a[v[i].x]=a[v[i-1].x]+i*(v[i].x-v[i-1].x);
for (j=v[i-1].x+1;j<v[i].x;++j)
a[j]=a[v[i-1].x]+i*(j-v[i-1].x);
}
for (i=N-2;i>=0;--i)
{
b[v[i].x]=b[v[i+1].x]+(N-i-1)*(v[i+1].x-v[i].x);
for (j=v[i+1].x-1;j>v[i].x;--j)
b[j]=b[v[i+1].x]+(N-i-1)*(v[i+1].x-j);
}
bst=MAX;
for (i=v[0].x;i<=v[N-1].x;++i)
if (a[i]+b[i+dx] < bst)
{
bst=a[i]+b[i+dx];
x1=i;
}
#ifdef DBG
for (i=v[0].x;i<=v[N-1].x;++i)
printf("%d ",a[i]);
printf("\n");
for (i=v[0].x;i<=v[N-1].x;++i)
printf("%d ",b[i]);
printf("\n\n");
#endif
//gata
//baleiez pe OY
sort(v.begin(),v.end(),cmpy);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (i=1;i<N;++i)
{
a[v[i].y]=a[v[i-1].y]+i*(v[i].y-v[i-1].y);
for (j=v[i-1].y+1;j<v[i].y;++j)
a[j]=a[v[i-1].y]+i*(j-v[i-1].y);
}
for (i=N-2;i>=0;--i)
{
b[v[i].y]=b[v[i+1].y]+(N-i-1)*(v[i+1].y-v[i].y);
for (j=v[i+1].y-1;j>v[i].y;--j)
b[j]=b[v[i+1].y]+(N-i-1)*(v[i+1].y-j);
}
bst=MAX;
for (i=v[0].y;i<=v[N-1].y;++i)
if (a[i]+b[i+dy] < bst)
{
bst=a[i]+b[i+dy];
y1=i;
}
#ifdef DBG
for (i=v[0].x;i<=v[N-1].x;++i)
printf("%d ",a[i]);
printf("\n");
for (i=v[0].x;i<=v[N-1].x;++i)
printf("%d ",b[i]);
printf("\n\n");
#endif
//gata , am coordonata coltului stang jos in x si y
#ifdef DBG
printf("%d %d\n",x1,y1);
#endif
//okay , sa computez distanta totala
x2=x1+dx; y2=y1+dy;
int cx,cy;
for (i=0;i<N;++i)
{
if ( v[i].x < x1 || x2 < v[i].x )
if (v[i].x > x2)
cx=v[i].x-x2;
else
cx=x1-v[i].x;
else
cx=0;
if ( v[i].y < y1 || y2 < v[i].y )
if (v[i].y > y2)
cy=v[i].y-y2;
else
cy=y1-v[i].y;
else
cy=0;
ret+=cx+cy;
}
printf("%d\n",ret);
return 0;
}