Pagini recente » Cod sursa (job #1160812) | Cod sursa (job #1509643) | Cod sursa (job #2489813) | Cod sursa (job #3222549) | Cod sursa (job #1017751)
#include <cstdio>
#include <cstdlib>
#define fr(i, a, b) for(int i=a; i<b; ++i)
#define INF 2147483647;
int n, dx, dy;
int x[500000];
int y[500000];
int minx = 50000, miny = 50000;
int maxx = 0, maxy = 0;
int ddx, ddy, hatar, min, max, k, km1;
int main()
{
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
scanf("%d%d%d", &n, &dx, &dy);
fr(i, 0, n)
{
scanf("%d%d", &x[i], &y[i]);
if (x[i]<minx) minx = x[i];
if (x[i]>maxx) maxx = x[i];
if (y[i]<miny) miny = y[i];
if (y[i]>maxy) maxy = y[i];
}
ddx = maxx-minx;
ddy = maxy-miny;
hatar = ddx-dx+1;
min = minx; max = maxx-dx;
while(min!=max)
{
maxx = 0;
float a = (float)(min+max)/2+0.5;
k = (int)a;
km1 = k-1;
fr(j, 0, n)
{
if (x[j]<k) maxx += k-x[j];
else if (x[j]>k+dx) maxx += x[j]-dx-k;
}
minx = 0;
fr(j, 0, n)
{
if (x[j]<km1) minx += km1-x[j];
else if (x[j]>km1+dx) minx += x[j]-dx-km1;
}
if (minx<maxx) max = km1;
else min = k;
}
if (minx>maxx) minx = maxx;
min = miny; max = maxy-dy;
while(min!=max)
{
maxy = 0;
float a = (float)(min+max)/2+0.5;
k = (int)a;
km1 = k-1;
fr(j, 0, n)
{
if (y[j]<k) maxy += k-y[j];
else if (y[j]>k+dy) maxy += y[j]-dy-k;
}
miny = 0;
fr(j, 0, n)
{
if (y[j]<km1) miny += km1-y[j];
else if (y[j]>km1+dy) miny += y[j]-dy-km1;
}
if (miny<maxy) max = km1;
else min = k;
}
if (miny>maxy) miny = maxy;
printf("%d", minx+miny);
return 0;
}