Pagini recente » Cod sursa (job #1865949) | Cod sursa (job #796329) | Rating Georgel Paduraru (alexboss622) | Cod sursa (job #388864) | Cod sursa (job #2466764)
//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;
}