Pagini recente » solutie/nrchei | Cod sursa (job #3289750) | Borderou de evaluare (job #996875) | Istoria paginii utilizator/florinc1996 | Cod sursa (job #171685)
Cod sursa(job #171685)
#include<fstream.h>
ifstream fin("tribute.in");
ofstream fout("tribute.out");
struct stare
{int nrst,nrdr,dst,ddr;}a[50001],b[50001];
struct pct
{int x,y;}s,p,pi,pf,max,min,suma;
int x[50001],y[50001],n,dx,dy,inf=100000;
int main()
{fin>>n>>dx>>dy;
int i;
min.x=min.y=inf;
s.x=s.y=inf;
for(i=1;i<=n;i++)
{fin>>p.x>>p.y;
x[p.x]++;
y[p.y]++;
suma.x+=p.x;
suma.y+=p.y;
if(p.x>max.x) max.x=p.x;
if(p.y>max.y) max.y=p.y;
if(p.x<min.x) min.x=p.x;
if(p.y<min.y) min.y=p.y;
}
suma.x-=n*min.x;
suma.y-=n*min.y;
a[min.x].nrdr=n-x[min.x];
a[min.x].ddr=suma.x;
for(i=min.x+1;i<=max.x;i++)
{a[i].dst=a[i-1].dst+n-a[i-1].nrdr;
a[i].ddr=a[i-1].ddr-a[i-1].nrdr;
a[i].nrst=n-a[i-1].nrdr;
a[i].nrdr=a[i-1].nrdr-x[i];
if(a[i].dst+a[i].ddr<s.x)
{s.x=a[i].dst+a[i].ddr;
p.x=i;
}
}
b[min.y].nrdr=n-y[min.y];
b[min.y].ddr=suma.y;
for(i=min.y+1;i<=max.y;i++)
{b[i].dst=b[i-1].dst+n-b[i-1].nrdr;
b[i].ddr=b[i-1].ddr-b[i-1].nrdr;
b[i].nrst=n-b[i-1].nrdr;
b[i].nrdr=b[i-1].nrdr-y[i];
if(b[i].dst+b[i].ddr<s.y)
{s.y=b[i].dst+b[i].ddr;
p.y=i;
}
}
pi=pf=p;
s.x=a[p.x].dst+a[p.x].ddr;
s.y=b[p.y].dst+b[p.y].ddr;
for(i=1;i<=dx;i++)
{if(pf.x==max.x) s.x=a[--pi.x].dst;
else
if(pi.x==min.x) s.x=a[++pf.x].ddr;
else
if(a[pi.x-1].dst-a[pi.x].dst<a[pf.x+1].ddr-a[pf.x].ddr) s.x+=a[pi.x-1].dst-a[pi.x--].dst;
else s.x+=a[pf.x+1].ddr-a[pf.x++].ddr;
}
for(i=1;i<=dy;i++)
{if(pf.y==max.y) s.y+=b[pi.y-1].dst-b[pi.y--].dst;
else
if(pi.y==min.y) s.y+=b[pf.y+1].ddr-b[pf.y++].ddr;
else
if(b[pi.y-1].dst-b[pi.y].dst<b[pf.y+1].ddr-b[pf.y].ddr) s.y+=b[pi.y-1].dst-b[pi.y--].dst;
else s.y+=b[pf.y+1].ddr-b[pf.y++].ddr;
}
fout<<s.x+s.y;
fin.close();
fout.close();
return 0;
}