Pagini recente » Cod sursa (job #60699) | Cod sursa (job #71033) | Cod sursa (job #2382593) | Cod sursa (job #2571725) | Cod sursa (job #122115)
Cod sursa(job #122115)
#include <cstdio>
#include <algorithm>
using namespace std;
struct dulap
{ long x; long y;};
long n,i,j,x[50010],y[50010],dx,dy,u,d,m;
dulap v[50010];
bool cmp1(dulap a, dulap b)
{
if (a.x<=b.x)
return true;
else
return false;
}
bool cmp2(dulap a, dulap b)
{
if (a.y<=b.y)
return true;
else
return false;
}
int main(){
freopen("tribute.in","r",stdin);
freopen("tribute.out","w",stdout);
scanf("%d%d%d",&n,&dx,&dy);
for (i=1;i<=n;i++)
scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp2);
//line sweeping pe orizontala
//prima data fac pentru linia 0 si vad ce distanta da
//la urmatoarele actualizez in O(1) in functie de cate se apropie si cate se departeaza
for (i=1;i<=n;i++)
if (v[i].y>dx)
{
x[0]+=(v[i].y-dx);
if (u==0)
u=i;
}
d=1;
//u--;
for (i=1;i<=50000;i++)
{
while ((v[d].y<i)&&(d<=n))
d++;
// printf("%d %d \n",d,u);
x[i]=x[i-1]+(d-1)-(n-u+1);
while ((v[u].y<=i+dx)&&(u<=n))
u++;
}
u=0;
sort(v+1,v+n+1,cmp1);
for (i=1;i<=n;i++)
if (v[i].x>dy)
{
y[0]+=(v[i].x-dy);
if (u==0)
u=i;
}
d=1;
//u--;
for (i=1;i<=50000;i++)
{
while ((v[d].x<i)&&(d<=n))
d++;
y[i]=y[i-1]+(d-1)-(n-u+1);
while ((v[u].x<=i+dy)&&(u<=n))
u++;
}
/*for (i=0;i<=5;i++)
printf("%d %d \n",x[i],y[i]);*/
/*m=x[0]+y[0];
for (i=1;i<=50000;i++)
if (x[i]+y[i]<m)
m=x[i]+y[i];*/
sort(x+1,x+50001);
sort(y+1,y+50001);
printf("%ld",x[1]+y[1]);
return 0;
}