Pagini recente » Cod sursa (job #1696905) | Cod sursa (job #357191) | Cod sursa (job #2086697) | Cod sursa (job #421362) | Cod sursa (job #1092437)
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_N = 50001;
int n, dx, dy;
int x[MAX_N], y[MAX_N];
void countSort(int a[], int n) {
int counts[MAX_N] = {0};
int sorted[n];
int min = MAX_N, max = 0;
for (int i = 1; i <= n; ++i) {
counts[a[i]]++;
if (a[i] > max) max = a[i];
if (a[i] < min) min = a[i];
}
// cumulate counts
for(int i = min; i <= max; i++){
counts[i] += counts[i-1];
}
// counts[i] now contains the number of elements <= i
for(int i = 1; i <= n; i++){
sorted[counts[a[i]]] = a[i];
counts[a[i]]--;
}
for(int i = 1; i <= n; i++){
// printf("%d " , sorted[i]);
a[i] = sorted[i];
}
// printf("\n");
}
int solve(int x[], int d, int n){
int sumLeft = 0;
int sumRight = 0;
int minSum = INT_MAX;
if (x[n] - x[1] <= d) return 0;
// compute distance for line at leftmost point
int leftIndex = 0; // first left index not covered by the line
int rightIndex = 0; // first right index that's not covered by the line
for(int i = 1; i <= n; i++){
if (x[i] > d) { rightIndex = i; break; }
}
for(int i = rightIndex; i <= n; i++){
sumRight += x[i];
}
minSum = sumLeft + sumRight;
// scan with movintg line segment 1 by 1 from left to right
for(int leftPosition = 1; leftPosition <= x[n] - d; ++leftPosition){
sumLeft += leftIndex;
sumRight -= (n - rightIndex + 1) ;
while(leftIndex + 1 <= n && x[leftIndex + 1] < leftPosition){
leftIndex++;
sumLeft += x[leftIndex];
}
while(rightIndex <= n && x[rightIndex] < leftPosition + d){
rightIndex++;
sumRight -= x[rightIndex];
}
if(sumLeft + sumRight < minSum) minSum = sumLeft + sumRight;
}
return minSum;
}
int main(int argc, char** argv) {
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]);
}
//countSort(x, n);
//countSort(y, n);
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
int minDistX, minDistY;
minDistX = solve(x, dx, n);
minDistY = solve(y, dy, n);
// printf("%d %d %d\n", minDistX, minDistY, minDistX + minDistY);
printf("%d\n", minDistX + minDistY);
return 0;
}