Cod sursa(job #1092439)

Utilizator IronWingVlad Paunescu IronWing Data 27 ianuarie 2014 00:50:10
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#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] - d;
    }
    minSum = sumLeft + sumRight;
    
    // scan with moving 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 += leftPosition - x[leftIndex];
        }
        while(rightIndex <= n && x[rightIndex] <= leftPosition + d){
            rightIndex++;
            sumRight -= x[rightIndex] - (leftPosition + d);
        }
        
        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;
}