Cod sursa(job #2466764)

Utilizator bluestorm57Vasile T bluestorm57 Data 2 octombrie 2019 21:40:23
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.83 kb
//wish me luck
//I'm ready for tle/wrong answer
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;
const int inf = 1e9;
struct Pair{
    int x,y,id;
} point[NMAX];
int dx,dy,n,dp[NMAX],dp2[NMAX],ans;
int dpx[NMAX],  dpy[NMAX];
int dpx2[NMAX], dpy2[NMAX];
int dpx3[NMAX], dpy3[NMAX];
int dpx4[NMAX], dpy4[NMAX];

bool cmp1(Pair X, Pair Y){
    return X.y < Y.y;
}

bool cmp2(Pair X, Pair Y){
    return X.x < Y.x;
}

void see(int dp[], int dp2[]){
    int i,j;
    for(i = 1 ; i <= n ; i++)
        g << dp[i] << " " ;
    g << "\n";
    for(i = 1 ; i <= n ; i++)
        g << dp2[i] << " " ;
}

void down_y(int dpy[]){
    int i,j;
    dp[0] = 0;
    dp2[n] = 0;
    for(i = 2 ; i <= n ; i++)
        dp[i] = dp[i - 1] + (point[i].y - point[i - 1].y) * (i - 1);
    j = 1;
    for(i = n - 1 ; i >= 1 ; i--,j++)
        dp2[i] = dp2[i + 1] + (point[i + 1].y - point[i].y) * j;
    j = 1;
    for(i = n - 1 ; i >= 1 ; i--, j++)
        if(point[i].y != point[i + 1].y)
            dp2[i] -= dy * j;
        else
            dp2[i] = dp2[i + 1];

    for(i = 1 ; i <= n ; i++)
        dpy[point[i].id] = dp[i] + dp2[i];
}

void up_y(int dpy[]){
    int i,j;
    dp[1] = 0;
    for(i = 2 ; i <= n ; i++)
        dp[i] = dp[i - 1] + (point[i].y - point[i - 1].y) * (i - 1);
    dp2[n] = 0;
    j = 1;
    for(i = n - 1 ; i >= 1 ; i--, j++){
        dp2[i] = dp2[i + 1] + (point[i + 1].y - point[i].y) * (j);
    }
    j = 1;
    for(i = 2 ; i <= n ; i++){
        j++;
        if(point[i].y != point[i - 1].y)
            dp[i] -= (j - 1) * dy;
        else
            dp[i] = dp[i - 1];
    }

    for(i = 1 ; i <= n ; i++)
        dpy[point[i].id] = dp[i] + dp2[i];
}

void left_x(int dpx[]){
    int i,j;
    dp[1] = 0;
    for(i = 2 ; i <= n ; i++){
        dp[i] = dp[i - 1] + (point[i].x - point[i - 1].x) * (i - 1);
    }
    dp2[n] = 0;
    j = 1;
    for(i = n - 1 ; i >= 1 ; i--, j++){
        dp2[i] = dp2[i + 1] + (point[i + 1].x - point[i].x) * (j);
    }

    j = 0;
    for(i = n - 1 ; i >= 1 ; i--){
        j++;
        if(point[i].x != point[i + 1].x)
            dp2[i] -= j * dx;
        else
            dp2[i] = dp2[i + 1];
    }
    for(i = 1 ; i <= n ; i++)
        dpx[point[i].id] = dp[i] + dp2[i];
}

void right_x(int dpx[]){
    int i,j;
    dp[1] = 0;
    for(i = 2 ; i <= n ; i++)
        dp[i] = dp[i - 1] + (point[i].x - point[i - 1].x) * (i - 1);
    dp2[n] = 0;
    j = 1;
    for(i = n - 1 ; i >= 1 ; i--, j++){
        dp2[i] = dp2[i + 1] + (point[i + 1].x - point[i].x) * (j);
    }

    for(i = 2 ; i <= n ; i++)
        if(point[i].x != point[i - 1].x)
            dp[i] -= dx * (i - 1);
        else
            dp[i] = dp[i - 1];

    for(i = 1 ; i <= n ; i++)
        dpx[point[i].id] = dp[i] + dp2[i];
}

int main(){
    int i,j,nr;
    f >> n >> dx >> dy;
    for(i = 1 ; i <= n ; i++){
        f >> point[i].x >> point[i].y;
        point[i].id = i;
    }

    /// y
    sort(point + 1, point + n + 1, cmp1);

    ///this is when the point is left down
    down_y(dpy);
    ///this is when the point is right down
    down_y(dpy2);
    ///this is when the point is left up
    up_y(dpy3);
    ///this is when the point is right up
    up_y(dpy4);

    ///x
    sort(point + 1, point + n + 1, cmp2);

    ///this is when the point is left down
    left_x(dpx);
    ///this is when the point is right down
    right_x(dpx2);
    ///this is when the point is left up
    left_x(dpx3);
    ///this is when the point is right up
    right_x(dpx4);

    ans = inf;
    for(i = 1 ; i <= n ; i++){
        ans = min(ans, min(min(min(dpx[i] + dpy[i], dpx2[i] + dpy2[i]), dpx3[i] + dpy3[i]), dpx4[i] + dpy4[i]));
    }
    g << ans;
    return 0;
}