Pagini recente » Cod sursa (job #2295166) | Cod sursa (job #556714)
Cod sursa(job #556714)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50005, INF = 2000000000;
int n, tot, dx, dy, x[N], y[N];
void read() {
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
scanf("%d %d %d", &n, &dx, &dy);
for (int i = 1; i <= n; ++ i)
scanf("%d %d", &x[i], &y[i]);
}
void init() {
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
}
void solvex() {
int xf = 0,xc = x[1] - 1, down = 0, in = 0, up = n, c = 0, rez = INF;
for (int i = 1; i <= n; ++ i)
c += x[i] - xc;
c += n;
while (xc <= x[n]) {
c += down - up;
if (c < rez) {
rez = c;
xf = xc;
}
while (x[down + in + 1] == xc + 1) {
++ in;
-- up;
-- c;
}
while (x[down + 1] == xc - dx) {
++ down;
-- in;
}
++ xc;
}
tot += rez;
}
void solvey() {
int yf = 0, yc = y[1] - 1, left = 0, in = 0, right = n, c = 0, rez = INF;
for (int i = 1; i <= n; ++ i)
c += y[i] - yc;
c += n;
while (yc <= y[n]) {
c += left - right;
if ( c < rez) {
rez = c;
yf = yc;
}
while (y[left + in + 1] == yc + 1) {
++ in;
-- right;
-- c;
}
while (y[left + 1] == yc - dy) {
++ left;
-- in;
}
++ yc;
}
tot += rez;
}
int main() {
read();
init();
solvex();
solvey();
printf("%d\n", tot);
return 0;
}