Pagini recente » Cod sursa (job #381353) | Cod sursa (job #1279428) | Cod sursa (job #369575) | Cod sursa (job #2168743) | Cod sursa (job #1259898)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
ifstream in("tribute.in");
ofstream out("tribute.out");
int n, dx, dy;
vector <int> x, y;
const int MAXN = 50000;
void citire()
{
in>>n>>dx>>dy;
for(int i = 1; i <= n; i++)
{
int p,q;
in>>p>>q;
x.push_back(p);
y.push_back(q);
}
}
int sweep( vector <int> &v, int lg )
{
if( v.size() == 1 )
return 0;
sort(v.begin(),v.end() );
int a = v[0], b = v[0] + lg;
int last = 0, first = -1;
int s[MAXN+2];
s[0] = v[0];
for(int i = 1; i < n; i++)
s[i] = s[i-1] + v[i];
int Smin = 0, aMin = 0;
for(int i = 0; i < n; i++)
if( v[i] < a )
Smin += (a-v[i]);
else if( b < v[i] )
Smin += (v[i]-b);
while( b <= v[n-1] )
{
while( v[first+1] < a )
first++;
while( last < n && v[last] <= b )
last++;
//dynamic;
int sLeft, sRight;
if( first == - 1 )
sLeft = 0;
else sLeft = a*(first+1) - s[first];
if( last == n )
sRight = 0;
else sRight = ( s[n-1] - s[last-1] ) - b*( n - last );//bookmark
Smin = min(sRight+sLeft,Smin);
a++, b++;
}
return Smin;
}
int main()
{
citire();
out<<sweep(x,dx) + sweep(y,dy);
return 0;
}