Pagini recente » Cod sursa (job #1079235) | Cod sursa (job #2814823) | Cod sursa (job #3223012) | Cod sursa (job #2336835) | Cod sursa (job #12512)
Cod sursa(job #12512)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 50000
FILE *f = fopen("pachete.in","rt"), *g = fopen("pachete.out","wt");
long int n,i,j,k,a[NMAX][2],x,y,b[NMAX][2],ord[NMAX],cy[NMAX],sol,pack[NMAX];
void citire()
{
fscanf(f,"%ld",&n);
fscanf(f,"%ld %ld",&x,&y);
for (i=1;i<=n;i++)
{fscanf(f,"%ld %ld",&a[i][0],&a[i][1]);
a[i][0]-=x;
a[i][1]-=y;
}
}
int cmp(const void *x, const void *y)
{
return a[ * (long int *) x ][0] - a[ * (long int *) y ][0];
}
long int count()
{
long int st,dr,mid,ls,ld;
for (i=1;i<=k;i++)
{if (b[i][0]<0) b[i][0]*=-1;
if (b[i][1]<0) b[i][1]*=-1;
ord[i]=i;}
qsort(ord,k+1,sizeof(long int),cmp);
for (i=1;i<=k;i++)
cy[i]=b[ord[i]][1];
memset(pack,0,sizeof(pack));
ld=1;pack[1]=cy[1];
for (i=2;i<=k;i++)
{
dr=ld;st=1;
if (pack[dr]>cy[i]) {ld++;pack[ld]=cy[i];}
else
{
while (st<dr)
{
mid=(st+dr)/2;
if (pack[mid]<cy[i]) dr=mid;
else if (pack[mid]==cy[i]) {st=mid;break;}
else st=mid-1;
}
pack[st]=cy[i];
}
}
return ld;
}
void solve()
{
//cadranul I
k=0;
for (i=1;i<=n;i++)
if (a[i][0]>0&&a[i][1]>0) {b[++k][0]=a[i][0];
b[k][1]=a[i][1];}
if (k) sol+=count();
//cadranul II
k=0;
for (i=1;i<=n;i++)
if (a[i][0]<0&&a[i][1]>0) {b[++k][0]=a[i][0];
b[k][1]=a[i][1];}
if (k) sol+=count();
//cadranul III
k=0;
for (i=1;i<=n;i++)
if (a[i][0]>0&&a[i][1]<0) {b[++k][0]=a[i][0];
b[k][1]=a[i][1];}
if (k) sol+=count();
//cadranul IV
k=0;
for (i=1;i<=n;i++)
if (a[i][0]<0&&a[i][1]<0) {b[++k][0]=a[i][0];
b[k][1]=a[i][1];}
if (k) sol+=count();
fprintf(g,"%ld",sol);
}
int main()
{
citire();
solve();
fclose(f);
fclose(g);
return 0;
}