Cod sursa(job #2466516)

Utilizator bluestorm57Vasile T bluestorm57 Data 2 octombrie 2019 14:34:36
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

const int NMAX = 50005;
const int inf = 1e9;
int n,dx,dy,ans;
pair <int, int> points[NMAX];

bool cmp(pair <int, int> X, pair <int, int> Y){
    if(X.first != Y.first)
        return X.first < Y.first;
    return X.second < Y.second;
}

int modul(int x){
    return max(x,-x);
}

int distance(int x, int y, int x2, int y2){
    return modul(x2 - x) + modul(y2 - y);
}

bool not_intersect(pair <int, int> X, pair <int, int> Y){
    if(Y.first >= X.first && Y.first <= X.first + dx && Y.second >= X.second && Y.second <= X.second + dy)
        return 0;
    return 1;
}

int main(){
    int i,j,dist,jf,js,xdx;
    f >> n >> dx >> dy;
    for(i = 1 ; i <= n ; i++){
        f >> points[i].first >> points[i].second;
    }
    sort(points + 1, points + n + 1, cmp);

    ans = inf;

    /// i is the upper left corner
    for(i = 1 ; i <= n ; i++){
        dist = 0;

        j = i - 1;
        while(points[i].first - dx <= points[j].first && j >= 1)
            j--;

        jf = max(1, j + 1);

        for(j ; j >= 1 ; j--)
            if(points[i].second >= points[j].second)
                dist += distance(points[i].first - dx ,points[i].second, points[j].first ,points[j].second);
            else
                if(points[i].second + dy <= points[j].second)
                    dist += distance(points[i].first - dx, points[i].second + dy, points[j].first, points[j].second);
                else
                    dist += distance(points[i].first - dx, 0, points[j].first, 0);

        j = i + 1;
        while(points[i].first == points[j].first && j <= n)
            j++;

        js = min(j - 1, n);

        for(j ; j <= n ; j++)
            if(points[i].second >= points[j].second)
                dist += distance(points[i].first, points[i].second, points[j].first, points[j].second);
            else
                if(points[j].second >= points[i].second + dy)
                    dist += distance(points[i].first, points[i].second + dy, points[j].first, points[j].second);
                else
                    dist += distance(points[i].first, 0, points[j].first, 0);


        for(j = jf ; j <= js ; j++)
            if(points[i].second >= points[j].second)
                dist += distance(0, points[i].second, 0, points[j].second);
            else
                if(points[j].second >= points[i].second + dy)
                    dist += distance(0, points[i].second + dy, 0, points[j].second);


        //g << dist << "\n";
        ans = min(ans, dist);
    }
    g << ans;

    return 0;
}