Pagini recente » Cod sursa (job #3793) | Cod sursa (job #3269158) | Cod sursa (job #290274) | Cod sursa (job #2601339) | Cod sursa (job #30319)
Cod sursa(job #30319)
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 50005
#define pct pair<int, int>
#define mp make_pair
#define x first
#define y second
int n, dx, dy;
pct punct[Nmax];
void citire()
{
int i, a, b;
scanf("%d %d %d\n", &n, &dx, &dy);
for (i = 1; i <= n; ++i)
{
scanf("%d %d\n", &a, &b);
punct[i] = mp(a, b);
}
}
int finddist(int d)
{
int i, st, dr, ret, nr1, nr2, dist;
// baleiere pt cazul cand terenul atinge un punct in stanga
st = 1;
dr = 1;
while (dr < n && punct[dr + 1].x - punct[st].x <= d)
++dr;
dist = 0;
nr1 = 0;
nr2 = n - dr;
for (i = dr + 1; i <= n; ++i)
dist += punct[i].x - punct[st].x - d;
ret = dist;
for (st = 2; st <= n; ++st)
{
++nr1;
dist += nr1 * (punct[st].x - punct[st - 1].x);
while (dr < n && punct[dr + 1].x - punct[st].x <= d)
{
++dr;
dist -= punct[dr].x - punct[st - 1].x - d;
--nr2;
}
dist -= nr2 * (punct[st].x - punct[st - 1].x);
if (dist < ret)
ret = dist;
}
reverse(punct+1, punct+n+1);
// baleiere pt cazul cand terenul atinge un punct in dreapta
st = 1;
dr = 1;
while (dr < n && punct[st].x - punct[dr + 1].x <= d)
++dr;
dist = 0;
nr1 = 0;
nr2 = n - dr;
for (i = dr + 1; i <= n; ++i)
dist += punct[st].x - punct[i].x - d;
if (dist < ret)
ret = dist;
for (st = 2; st <= n; ++st)
{
++nr1;
dist += nr1 * (punct[st - 1].x - punct[st].x);
while (dr < n && punct[st].x - punct[dr + 1].x <= d)
{
++dr;
dist -= punct[st - 1].x - punct[dr].x - d;
--nr2;
}
dist -= nr2 * (punct[st - 1].x - punct[st].x);
if (dist < ret)
ret = dist;
}
return ret;
}
void solve()
{
int sol = 0, i;
sort(punct+1, punct+n+1);
sol += finddist(dx);
for (i = 1; i <= n; ++i)
swap(punct[i].x, punct[i].y);
sort(punct+1, punct+n+1);
sol += finddist(dy);
printf("%d\n", sol);
}
int main()
{
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
citire();
solve();
return 0;
}