Pagini recente » Cod sursa (job #635062) | Cod sursa (job #1607510)
#include <algorithm>
#include <fstream>
#include <cstdio>
#define INF 1000000000
#define NMAX 50005
using namespace std;
int n , dx , dy , soly = INF , solx = INF , mx , my , inc , sf , nr;
int vx[NMAX] , vy[NMAX] , sumst[NMAX] , sumdr[NMAX];
void read(int &x) {
bool sign = 1;
char ch;
while(!isdigit(ch = getchar())) {
if(ch == '-')
sign = -1;
else
sign = 1;
}
do {
x = x * 10 + ch - '0';
}while(isdigit(ch = getchar()));
x *= sign;
}
int caut_bin(int val , bool x , int v[]);
int main() {
freopen("tribute.in" , "r" , stdin);
freopen("tribute.out" , "w" , stdout);
read(n) , read(dx) , read(dy);
for(int i = 1 ; i <= n ; ++i) {
read(vx[i]) , read(vy[i]);
mx = max(mx , vx[i]);
my = max(my , vy[i]);
}
sort(vx + 1 , vx + n + 1);
for(int i = 1 ; i <= n ; ++i) {
sumst[i] = sumst[i - 1] + mx - vx[i];
}
for(int i = n ; i >= 1 ; --i) {
sumdr[i] = sumdr[i + 1] + vx[i];
}
for(int i = 0 ; i <= mx ; ++i) {
inc = i;
sf = i + dx;
int p1 = caut_bin(sf , 1 , vx);
int p2 = caut_bin(inc , 0 , vx);
nr = sumdr[p1] - sf * (n - p1 + 1) + sumst[p2] - (mx - inc) * p2;
solx = min(solx , nr);
}
sort(vy + 1 , vy + n + 1);
sumst[0] = 0;
for(int i = 1 ; i <= n ; ++i) {
sumst[i] = sumst[i - 1] + my - vy[i];
}
sumdr[n + 1] = 0;
for(int i = n ; i >= 1 ; --i) {
sumdr[i] = sumdr[i + 1] + vy[i];
}
for(int i = 0 ; i <= my ; ++i) {
inc = i;
sf = i + dy;
int p1 = caut_bin(sf , 1 , vy);
int p2 = caut_bin(inc , 0 , vy);
nr = sumdr[p1] - sf * (n - p1 + 1) + sumst[p2] - (my - inc) * p2;
soly = min(soly , nr);
}
printf("%d" , solx + soly);
return 0;
}
int caut_bin(int val , bool x , int v[]) {
int i , p = 0;
for(i = 1 ; i <= n ; i <<= 1);
while(i) {
if(i + p <= n && v[i + p] <= val) {
p += i;
}
i >>= 1;
}
if(x == 1) {
++p;
}
return p;
}