Pagini recente » Cod sursa (job #838405) | Cod sursa (job #2390025) | Cod sursa (job #3124563) | Cod sursa (job #827133) | Cod sursa (job #78265)
Cod sursa(job #78265)
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
#define NMAX 390010
int x[NMAX], y[NMAX];
int n, dx, dy;
int minx, miny;
void read()
{
int i;
scanf("%d%d%d", &n, &dx, &dy);
for(i = 1; i <= n; ++i)
scanf("%d%d", x+i, y+i);
}
#define MIN(a, b) ((a) < (b)) ? (a) : (b)
#define ABS(a) ((a) > 0) ? (a) : -(a)
//#define umm(
int solve(int x[NMAX], int d)
{
int i, j;
int first, last, t;
int currentMin = 2000000000;
int before[NMAX], after[NMAX];
#define after (after + 10000)
#define before (before + 10000)
memset(before, 0, sizeof(before));
memset(after, 0, sizeof(after));
for(i = x[1], j = 1, t = 0; i <= x[n]; ++i)
{
after[i] = ((i > 0) ? (after[i-1]) : 0) + t;
while(i == x[j])
j++, ++t;
//printf("%d ", after[i]);
}
//printf("\n\n");
for(i = x[n], j = n, t = 0; i >= x[1]; --i)
{
before[i] = before[i+1] + t;
while(i == x[j])
j--, ++t;
//printf("%d ", before[i]);
}
//printf("\n\n");
for(i = x[1]; i < NMAX && i <= n; ++i)
{
currentMin = MIN(currentMin, after[i] + before[i+d]);
}
return currentMin;
}
int main()
{
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
read();
sort(x+1, x+n+1);
sort(y+1, y+n+1);
minx = solve(x, dx);
miny = solve(y, dy);
printf("%d\n", minx+miny);
return 0;
}