Cod sursa(job #30319)

Utilizator victorsbVictor Rusu victorsb Data 13 martie 2007 19:04:44
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 50005
#define pct pair<int, int>
#define mp make_pair
#define x first
#define y second

int n, dx, dy;
pct punct[Nmax];

void citire()
{
    int i, a, b;
    
    scanf("%d %d %d\n", &n, &dx, &dy);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d\n", &a, &b);
        punct[i] = mp(a, b);
    }
}

int finddist(int d)
{
    int i, st, dr, ret, nr1, nr2, dist;
    
    
    // baleiere pt cazul cand terenul atinge un punct in stanga
    st = 1;
    dr = 1;
    while (dr < n && punct[dr + 1].x - punct[st].x <= d)
        ++dr;
    
    dist = 0;
    nr1 = 0;
    nr2 = n - dr;
    for (i = dr + 1; i <= n; ++i)
        dist += punct[i].x - punct[st].x - d;
    ret = dist;
    
    for (st = 2; st <= n; ++st)
    {
        ++nr1;
        dist += nr1 * (punct[st].x - punct[st - 1].x);
        while (dr < n && punct[dr + 1].x - punct[st].x <= d)
        {
            ++dr;
            dist -= punct[dr].x - punct[st - 1].x - d;
            --nr2;
        }
        dist -= nr2 * (punct[st].x - punct[st - 1].x);
        if (dist < ret)
            ret = dist;
    }
    
    reverse(punct+1, punct+n+1);
    
    // baleiere pt cazul cand terenul atinge un punct in dreapta
    st = 1;
    dr = 1;
    while (dr < n && punct[st].x - punct[dr + 1].x <= d)
        ++dr;
    
    dist = 0;
    nr1 = 0;
    nr2 = n - dr;
    for (i = dr + 1; i <= n; ++i)
        dist += punct[st].x - punct[i].x - d;
    if (dist < ret)
       ret = dist;
    
    for (st = 2; st <= n; ++st)
    {
        ++nr1;
        dist += nr1 * (punct[st - 1].x - punct[st].x);
        while (dr < n && punct[st].x - punct[dr + 1].x <= d)
        {
            ++dr;
            dist -= punct[st - 1].x - punct[dr].x - d;
            --nr2;
        }
        dist -= nr2 * (punct[st - 1].x - punct[st].x);
        if (dist < ret)
            ret = dist;
    }
    
    return ret;
}

void solve()
{
    int sol = 0, i;
    
    sort(punct+1, punct+n+1);
    sol += finddist(dx);
    
    for (i = 1; i <= n; ++i)
        swap(punct[i].x, punct[i].y);
    
    sort(punct+1, punct+n+1);
    sol += finddist(dy);
    
    printf("%d\n", sol);
}

int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);
    citire();
    solve();
    return 0;
}