Cod sursa(job #12512)

Utilizator devilkindSavin Tiberiu devilkind Data 4 februarie 2007 11:37:59
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#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;
}