Pagini recente » Cod sursa (job #106999) | Cod sursa (job #1541100) | Cod sursa (job #2547371) | Cod sursa (job #2547410) | Cod sursa (job #2641734)
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin( "tribute.in" );
ofstream fout( "tribute.out" );
const int MaxN = 50002;
int x[MaxN], y[MaxN];
int xs[MaxN], ys[MaxN];
int maxx[MaxN], maxy[MaxN];
int cautbin( int v[], int e, int n, int ind ) {
int step;
for ( step = 1; step <= n; step <<= 1 );
for ( ; step > 0; step >>= 1 ) {
if ( ind + step <= n ) {
if ( v[ind + step] <= e ) {
ind += step;
}
}
}
return ind;
}
int main() {
int n, dx, dy, i, px, py, p;
fin >> n >> dx >> dy;
for ( i = 1; i <= n; ++i ) {
fin >> x[i] >> y[i];
}
sort( x + 1, x + n + 1 );
sort( y + 1, y + n + 1 );
for ( i = 1; i <= n; ++i ) {
xs[i] = xs[i - 1] + x[i];
ys[i] = ys[i - 1] + y[i];
}
long long sol = 2500000000;
for ( i = 1; i <= n; ++i ) {
px = cautbin( x, x[i] + dx - 1, n, i );
py = cautbin( y, y[i] + dy - 1, n, i );
p = min( px, py );
if ( !( x[p] <= x[i] + dx - 1 && y[p] <= y[i] + dy - 1 ) ) {
p = i;
}
int r = ((i - 1) * x[i] - xs[i - 1] + xs[n] - xs[p] - (n - p) * x[i]) + ((i - 1) * y[i - 1] - ys[i - 1] + ys[n] - ys[p] - (n - p) * y[i]);
//printf( "%d\n", r );
if ( sol > r ) {
sol = r;
}
}
fout << sol;
fin.close();
fout.close();
return 0;
}