Pagini recente » Cod sursa (job #3151078) | Cod sursa (job #1257596)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <iterator>
using namespace std;
ifstream in("tribute.in");
ofstream out("tribute.out");
const int MAXN = 50000;
long long N, DX, DY, px[MAXN+1], py[MAXN+1];
void citire()
{
in>>N>>DX>>DY;
for(int i = 1; i <= N; i++)
in>>px[i]>>py[i];
}
long long sweep(long long p[MAXN+1], long long lg)
{
long long sp[MAXN+1];
sort(p+1,p+N+1);
sp[0] = 0;
for(int i = 1; i <= N; i++)
sp[i] = sp[i-1] + p[i];
//for(int i = 1; i <= N; i++)
// cout<<p[i]<<' ';
//cout<<endl<<endl;
long long first, last;
deque <int> E;
long long i = 1;
while( p[i] <= p[1] + lg )
E.push_back(i++);
long long a = p[E.front()], b = p[1] + lg;
long long smin = 2000000;
while( b <= p[N] )
{
if( E.empty() == false )
{
long long sc = ( sp[N] - sp[ E.back() ] - b*(N-E.back()) )+( a*(E.front()-1) - sp[ E.front() - 1] );
if( sc < smin )
smin = sc;
//cout<<a<<' '<<b<<' '<<sc<<' '<<' ';
}
//for( deque <int>::iterator i = E.begin(); i != E.end(); i++)
// cout<<*i<<' ';
//cout<<endl;
a++;
b++;
while( p[ E.front() ] < a && E.empty() == false )
E.pop_front();
while( p[ E.back() + 1 ] <= b && E.back() + 1 <= N )
E.push_back( E.back() + 1 );
}
return smin;
}
int main()
{
citire();
out<<sweep(py,DY)+sweep(px,DX);
return 0;
}