Cod sursa(job #598018)

Utilizator cosmyoPaunel Cosmin cosmyo Data 24 iunie 2011 13:45:40
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50005;
typedef long long ll;
pair<ll, ll> a[N];
ll n, X[N], Y[N], sx[N], sy[N], DX, DY;

ll solve1(ll DX, ll DY) {
    ll min = 1000000000, i1, i2 = 0, sol, y1, y2;
    for(i1 = 1; i1 <= n; ++i1) {
        while(X[i2] <= a[i1].first + DX)
            ++i2;
        sol = abs(sx[i1] - a[i1].first * i1) + sx[n] - sx[i2 - 1] - (X[i1] + DX) * (n - i2 + 1);
     //   printf("%d ",sol);
        y1 = lower_bound(Y , Y + n + 1, a[i1].second) - Y;
        y2 = lower_bound(Y , Y + n + 1, a[i1].second + DY) - Y;
        sol += abs(sy[y1] - y1 * a[i1].second) + sy[n] - sy[y2 - 1] - (a[i1].second + DY) * (n - y2 + 1);
     //   printf("%d %d\n", sol, i2);
        if(sol < min)
            min = sol;
    }

    return min;
}

ll solve2(ll DX, ll DY) {
    ll min = 1000000000, i1, i2 = 0, sol, y1, y2;
    for(i1 = 1; i1 <= n; ++i1) {
        while(X[i2] <= a[i1].first - DX)
            ++i2;
        --i2;
        sol = abs(sx[i2] - (X[i1] - DX) * i2) + sx[n] - sx[i1] - X[i1] * (n - i1);
     //   printf("%d ", sol);
        y1 = lower_bound(Y , Y + n + 1, a[i1].second - DY) - Y ;
        y2 = lower_bound(Y , Y + n + 1, a[i1].second) - Y;
        sol += abs(sy[y1 - 1] - (y1 - 1) * (a[i1].second - DY)) + sy[n] - sy[y2] - (a[i1].second) * (n - y2);
     //   if(sol < min)
      //  printf("%d %d\n",sol, y1);
        if(sol < min)
            min = sol;
    }

    return min;
}
ll solve3(ll DX, ll DY) {
    ll min = 1000000000, i1, i2 = 0, sol, y1, y2;
    for(i1 = 1; i1 <= n; ++i1) {
        while(X[i2] <= a[i1].first - DX)
            ++i2;
        --i2;
        sol = abs(sx[i2] - (X[i1] - DX) * i2) + sx[n] - sx[i1] - X[i1] * (n - i1);
      //  printf("%d ", sol);
        y1 = lower_bound(Y , Y + n + 1, a[i1].second) - Y;
        y2 = lower_bound(Y , Y + n + 1, a[i1].second + DY) - Y;
        sol += abs(sy[y1] - y1 * a[i1].second) + sy[n] - sy[y2 - 1] - (a[i1].second + DY) * (n - y2 + 1);
      //  printf("%d %d\n", y2, sol);
        if(sol < min)
            min = sol;
    }

    return min;
}

ll solve4(ll DX, ll DY) {
    int min = 1000000000, i1, i2 = 0, sol, y1, y2;
    for(i1 = 1; i1 <= n; ++i1) {
        while(X[i2] <= a[i1].first + DX)
            ++i2;
        sol = abs(sx[i1] - a[i1].first * i1) + sx[n] - sx[i2 - 1] - (X[i1] + DX) * (n - i2 + 1);
    //    printf("%d ", sol);
        y1 = lower_bound(Y , Y + n + 1, a[i1].second - DY) - Y ;
        y2 = lower_bound(Y , Y + n + 1, a[i1].second) - Y;
        sol += abs(sy[y1 - 1] - (y1 - 1) * (a[i1].second - DY)) + sy[n] - sy[y2] - (a[i1].second) * (n - y2);

      //  printf("%d %d\n", y1, sol);
        if(sol < min)
            min = sol;
    }

    return min;
}
int main() {
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);
    ll i;
    scanf("%Ld %Ld %Ld", &n, &DX, &DY);
    for(i = 1; i <= n; ++i)
        scanf("%Ld %Ld", &a[i].first, &a[i].second), X[i] = a[i].first, Y[i] = a[i].second  ;
    sort(a + 1, a + n + 1);
    sort(X + 1, X + n + 1);
    sort(Y + 1, Y + n + 1);
    X[n + 1] = Y[n + 1] = 1000000000;
    for(i = 1; i <= n ; ++i){
        sx[i] = sx[i - 1] + X[i];
        sy[i] = sy[i - 1] + Y[i];
    }
       X[0] = Y[0] = -50000000;
    ll min = solve1(DX, DY);
 //   printf("\n");
    ll sl = solve2(DX, DY);
  //  printf("\n", sl);

    if(min > sl)
        min = sl;
    sl = solve3(DX, DY);
    if(min > sl)
        min = sl;
  //  printf("\n");
    sl = solve4(DX, DY);

    if(min > sl)
        min = sl;
    printf("%Ld\n", min);

    return 0;
}