Pagini recente » Cod sursa (job #3320667) | Cod sursa (job #3319449) | Cod sursa (job #3337475) | Cod sursa (job #3304338) | Cod sursa (job #3327052)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
bool desc(int a,int b)
{
return a>b;
}
long long x[50005],y[50005],prefx[50005],prefy[50005],mnx = 1e18, mny = 1e18;
int j=1;
int main()
{
int n,dx,dy;
fin>>n>>dx>>dy;
for(int i=1;i<=n;i++)
{
fin>>x[i]>>y[i];
}
sort(x+1,x+n+1);
for(int i=1;i<=n;i++)
{
prefx[i]=prefx[i-1]+x[i];
}
sort(y+1,y+n+1);
for(int i=1;i<=n;i++)
{
prefy[i]=prefy[i-1]+y[i];
}
for(int i=1;i<=n;i++)
{
while(j+1<=n && x[j+1]<=x[i]+dx-1)
j++;
long long cost_st,cost_dr,cost_tot;
cost_st=x[i]*(i-1)-prefx[i-1];
cost_dr=(prefx[n]-prefx[j])-(x[i]+dx)*(n-j);
cost_tot=cost_st+cost_dr;
//cout<<i<<" "<<j<<" "<<x[i]<<" "<<x[j]<<" "<<cost_tot<<endl;
if(cost_tot<mnx)
mnx=cost_tot;
}
j=1;
sort(x+1,x+n+1,desc);
for(int i=1;i<=n;i++)
{
prefx[i]=prefx[i-1]+x[i];
}
for(int i=1;i<=n;i++)
{
while(j+1<=n && x[j+1]>=x[i]-dx+1)
j++;
long long cost_st,cost_dr,cost_tot;
cost_st=-(x[i]*(i-1)-prefx[i-1]);
cost_dr=-((prefx[n]-prefx[j])-(x[i]-dx)*(n-j));
cost_tot=cost_st+cost_dr;
//cout<<i<<" "<<j<<" "<<x[i]<<" "<<x[j]<<" "<<cost_tot<<endl;
if(cost_tot<mnx)
mnx=cost_tot;
}
j=1;
for(int i=1;i<=n;i++)
{
while(j+1<=n && y[j+1]<=y[i]+dy-1)
j++;
long long cost_st,cost_dr,cost_tot;
cost_st=y[i]*(i-1)-prefy[i-1];
cost_dr=(prefy[n]-prefy[j])-(y[i]+dy)*(n-j);
cost_tot=cost_st+cost_dr;
if(cost_tot<mny)
mny=cost_tot;
}
j=1;
sort(y+1,y+n+1,desc);
for(int i=1;i<=n;i++)
{
prefy[i]=prefy[i-1]+y[i];
}
for(int i=1;i<=n;i++)
{
while(j+1<=n && y[j+1]>=y[i]-dy+1)
j++;
long long cost_st,cost_dr,cost_tot;
cost_st=-(y[i]*(i-1)-prefy[i-1]);
cost_dr=-((prefy[n]-prefy[j])-(y[i]-dy)*(n-j));
cost_tot=cost_st+cost_dr;
if(cost_tot<mny)
mny=cost_tot;
}
fout<<mnx+mny;
return 0;
}