Pagini recente » Cod sursa (job #1753391) | Cod sursa (job #1551287) | Cod sursa (job #2406874) | Cod sursa (job #2217239) | Cod sursa (job #1741379)
#include<bits/stdc++.h>
#define maxN 50005
//#define INF INT_MAX
using namespace std;
pair<int,int> v[maxN];
long long best=LLONG_MAX,minim,minim1,s[maxN],d[maxN],s1[maxN],d1[maxN];
int imin,jmin;
int isx[maxN],isy[maxN],puncte[maxN],puncte2[maxN],xmax,ymax,n,dx,dy,puncte3[maxN],puncte4[maxN];
inline int max(int a,int b)
{
return a>b?a:b;
}
void generarex()
{
if (isx[0]) puncte[0]=isx[0];
for(int i=1;i<=xmax;i++)
{
puncte[i]=puncte[i-1]+isx[i];
}
s[0]=0;
for(int i=1;i<=xmax;i++)
s[i]=s[i-1]+1LL*puncte[i-1];
if (isx[xmax]) puncte2[xmax]=isx[xmax];
for(int i=xmax-1;i>=0;i--)
{
puncte2[i]=puncte2[i+1]+isx[i];
}
d[xmax]=0;
for(int i=xmax-1;i>=0;i--)
{
d[i]=d[i+1]+1LL*puncte2[i+1];
}
}
void generarey()
{
if (isy[0]) puncte3[0]=isy[0];
for(int i=1;i<=ymax;i++)
{
puncte3[i]=puncte3[i-1]+isy[i];
}
s1[0]=0;
for(int i=1;i<=ymax;i++)
s1[i]=s1[i-1]+1LL*puncte3[i-1];
if (isy[ymax]) puncte4[ymax]=isy[ymax];
for(int i=ymax-1;i>=0;i--)
{
puncte4[i]=puncte4[i+1]+isy[i];
}
d1[ymax]=0;
for(int i=ymax-1;i>=0;i--)
{
d1[i]=d1[i+1]+1LL*puncte4[i+1];
}
}
void solve(int dx,int dy)
{
minim=LLONG_MAX;
for(int i=0;i<=(xmax);i++)
{
if (1LL*(s[i]+d[i+dx])<minim)
{
minim=(s[i]+d[i+dx])*1LL;
imin=i;
}
}
minim1=LLONG_MAX;
for(int i=0;i<=(ymax);i++)
{
if (1LL*(s1[i]+d1[i+dy])<minim1)
{
minim1=(s1[i]+d1[i+dy])*1LL;
jmin=i;
}
}
if (((minim+minim1)*1LL)<best)
{
best=1LL*(minim+minim1);
}
}
int main()
{
freopen("tribute.in","r",stdin);
freopen("tribute.out","w",stdout);
scanf("%d%d%d",&n,&dx,&dy);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i].first,&v[i].second);
isx[v[i].first]++;
isy[v[i].second]++;
xmax=max(xmax,v[i].first);
ymax=max(ymax,v[i].second);
}
generarex();
generarey();
solve(dx,dy);
// if (dx!=dy) solve(dy,dx);
printf("%lld\n",best);
return 0;
}