Pagini recente » Cod sursa (job #633043) | Cod sursa (job #2012280)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct miau{int x,y;} v[50005];
int n,i,j,X,Y,hdist,vdist,dx,dy,minhdist,minvdist,cresc, descresc,l,r;
ifstream f("tribute.in");
ofstream g("tribute.out");
bool cmpx(miau a, miau b)
{
return a.x<b.x;
}
bool cmpy(miau a, miau b)
{
return a.y<b.y;
}
int main()
{
f>>n>>dx>>dy;
for(i=1;i<=n;i++) f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmpx);
X=0; Y=0; cresc=0; descresc=0;
for(i=1;i<=n;i++)
if(v[i].x<=X) hdist+=X-v[i].x, cresc++;
else if(v[i].x>X+dx) hdist+=v[i].x-X-dx, descresc++;
minhdist=hdist;
l=1; r=1;
while(v[l].x<=X && l<=n) l++;
while(v[r].x<X+dx && r<=n) r++;
for(i=1;i<=50000;i++)
{
X++;
hdist+=cresc;
hdist-=descresc;
if(hdist<minhdist) minhdist=hdist;
while(l<=n && v[l].x==X) l++, cresc++;
while(r<=n && v[r].x==X+dx) r++, descresc--;
}
sort(v+1,v+n+1,cmpy);
cresc=0; descresc=0;
for(i=1;i<=n;i++)
if(v[i].y<=Y) vdist+=Y-v[i].y, cresc++;
else if(v[i].y>Y+dy) vdist+=v[i].y-Y-dy, descresc++;
minvdist=vdist;
l=1;r=1;
while(v[l].y<=Y && l<=n) l++;
while(v[r].y<Y+dy && r<=n) r++;
for(i=1;i<=50000;i++)
{
Y++;
vdist+=cresc;
vdist-=descresc;
if(vdist<minvdist) minvdist=vdist;
while(l<=n && v[l].y==Y) l++, cresc++;
while(r<=n && v[r].y==Y+dy) r++, descresc--;
}
g<<minhdist+minvdist<<'\n';
return 0;
}