Pagini recente » Cod sursa (job #1338864) | Cod sursa (job #1702368) | Cod sursa (job #562784) | Cod sursa (job #1714797) | Cod sursa (job #2467110)
//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 n,dx,dy,ans;
int dp[NMAX],dp2[NMAX];
int dpx2[NMAX], dpx3[NMAX];
int dpy2[NMAX], dpy3[NMAX];
void see(int v[]){
int i;
for(i = 1 ; i <= n ; i++)
g << v[i] << " ";
g << "\n";
}
bool cmp1(Pair X, Pair Y){
return X.y < Y.y;
}
bool cmp2(Pair X, Pair Y){
return X.x < Y.x;
}
void up_y(int dpy[]){
int i,j,value,dif;
j = 1;
dp2[n] = 0;
for(i = n - 1 ; i >= 1 ; i--, j++){
dp2[i] = dp2[i + 1] + (point[i + 1].y - point[i].y) * j;
}
dp[1] = 0;
for(i = 2 ; i <= n ; i++){
dp[i] = 0;
value = point[i].y - dy;
for(j = i - 1 ; j >= 1 ; j--){
dif = value - point[j].y;
if(dif > 0)
dp[i] += dif;
}
}
for(i = 1 ; i <= n ; i++)
dpy[i] = dp[i] + dp2[i];
}
void down_y(int dpy[]){
int i,j,value,dif;
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;
for(i = n - 1 ; i >= 1 ; i--){
dp2[i] = 0;
value = point[i].y + dy;
for(j = i + 1 ; j <= n ; j++){
dif = point[j].y - value;
if(dif > 0)
dp2[i] += dif;
}
}
for(i = 1 ; i <= n ; i++)
dpy[i] = dp[i] + dp2[i];
}
void left_x(int dpx[]){
int i,j,value,dif;
dp[1] = 0;
for(i = 1 ; i <= n ; i++)
dp[i] = dp[i - 1] + (point[i].x - point[i - 1].x) * (i - 1);
dp2[n] = 0;
for(i = n - 1 ; i >= 1 ; i--){
dp2[i] = 0;
value = point[i].x + dx;
for(j = i + 1 ; j <= n ; j++){
dif = point[j].x - value;
if(dif > 0)
dp2[i] += dif;
}
}
for(i = 1 ; i <= n ; i++)
dpx[i] = dp[i] + dp2[i];
}
void right_x(int dpx[]){
int i,j,dif,value;
dp[1] = 0;
for(i = 2 ; i <= n ; i++){
dp[i] = 0;
value = point[i].x - dx;
for(j = i - 1 ; j >= 1 ; j--){
dif = value - point[j].x;
if(dif > 0)
dp[i] += dif;
}
}
j = 1;
dp2[n] = 0;
for(i = n - 1 ; i >= 1 ; i--, j++)
dp2[i] = dp2[i + 1] + (point[i + 1].x - point[i].x) * j;
for(i = 1 ; i <= n ; i++)
dpx[i] = dp[i] + dp2[i];
}
int main(){
int i;
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);
up_y(dpy2);
down_y(dpy3);
///x;
sort(point + 1, point + n + 1, cmp2);
left_x(dpx2);
right_x(dpx3);
ans = inf;
for(i = 1 ; i <= n ; i++){
ans = min(ans, dpx2[i] + dpy2[i]);
ans = min(ans, dpx2[i] + dpy3[i]);
ans = min(ans, dpx3[i] + dpy2[i]);
ans = min(ans, dpx3[i] + dpy3[i]);
}
g << ans;
return 0;
}