Pagini recente » Cod sursa (job #3134060) | Cod sursa (job #1707859) | Cod sursa (job #375274) | Cod sursa (job #2208180)
#include <bits/stdc++.h>
using namespace std;
int n, dx, dy;
struct aib{
int v[50005];
int nr[50005];
inline void U(int val, int pos){
for(int i = pos; i <= 50002 ; i += (i & (-i))){
v[i] += val;
nr[i] += 1;
}
}
inline pair <int, int> Q(int pos){
pair <int, int> ans;
for(int i = pos; i != 0 ; i -= (i & (-i))){
ans.first += v[i];
ans.second += nr[i];
}
return ans;
}
};
aib ax;
aib ay;
int main()
{
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
scanf("%d%d%d", &n, &dx, &dy);
++dx; ++dy;
int x, y;
for(int i = 1; i <= n ; ++i){
scanf("%d%d", &x, &y);
++x; ++y;
ax.U(x, x); ay.U(y, y);
}
long long solx = 1000000000000000000;
long long val;
pair <int, int> aux;
pair <int, int> aux2;
for(int i = 1; i <= 50001 - dx + 1; ++i){
val = 0;
aux = ax.Q(i - 1);
val = val + (1LL * aux.second * i - aux.first);
aux2 = ax.Q(50001);
aux = ax.Q(i + dx - 1);
aux2.first -= aux.first;
aux2.second -= aux.second;
val = val + (aux2.first - 1LL * aux2.second * (i + dx - 1));
if(val < solx) solx = val;
}
long long soly = 1000000000000000000;
for(int i = 1; i <= 50001 - dy + 1; ++i){
val = 0;
aux = ay.Q(i - 1);
val = val + (1LL * aux.second * i - aux.first);
aux2 = ay.Q(50001);
aux = ax.Q(i + dy - 1);
aux2.first -= aux.first;
aux2.second -= aux.second;
val = val + (aux2.first - 1LL * aux2.second * (i + dy - 1));
if(val < soly) soly = val;
}
printf("%lld", solx + soly);
return 0;
}