Pagini recente » Cod sursa (job #2468601) | Cod sursa (job #2175721) | Cod sursa (job #475863) | Cod sursa (job #737742) | Cod sursa (job #8921)
Cod sursa(job #8921)
#include <stdio.h>
#include <string.h>
int n,xp,yp,x[50000],y[50000],h[50000],ult[50000];
void qSort(int st, int dr)
{
int i=st, j=dr, m=x[h[(i+j)/2]];
do
{
while (x[h[i]]<m) i++;
while (x[h[j]]>m) j--;
if (i<=j)
{
int aux=x[h[i]]; x[h[i]]=x[h[j]]; x[h[j]]=aux;
aux=y[h[i]]; y[h[i]]=y[h[j]]; y[h[j]]=aux;
i++; j--;
}
}
while (i<=j);
if (st<j) qSort(st,j);
if (i<dr) qSort(i,dr);
}
int main()
{
freopen("pachete.in","r",stdin);
scanf("%d %d %d\n",&n,&xp,&yp);
for (int i=0;i<n;i++) scanf("%d %d",&x[i],&y[i]);
int nrtot=0;
for (int ki=1;ki<=4;ki++)
{
int nr=0;
for (int i=0;i<n;i++)
switch (ki)
{
case 1: if (x[i]>xp && y[i]>yp) h[nr++]=i; break;
case 2: if (x[i]<xp && y[i]>yp) h[nr++]=i; break;
case 3: if (x[i]<xp && y[i]<yp) h[nr++]=i; break;
case 4: if (x[i]>xp && y[i]<yp) h[nr++]=i; break;
}
qSort(0,nr-1);
int cate=0;
for (int i=0;i<nr;i++)
{
int st=0, dr=cate-1, k=-1, aux=y[h[i]];
while (st<=dr)
{
int m=(st+dr)/2;
if (ult[m]>aux) st=m+1;
else k=m, dr=m-1;
}
if (k<0) ult[cate++]=aux;
else ult[k]=aux;
}
nrtot+=cate;
}
freopen("pachete.out","w",stdout);
printf("%d\n",nrtot);
fclose(stdout);
return 0;
}