Pagini recente » Cod sursa (job #751282) | Cod sursa (job #1955730) | Cod sursa (job #46176) | Cod sursa (job #1217060) | Cod sursa (job #22967)
Cod sursa(job #22967)
#include<fstream.h>
int long cadr[5][2][50002],nr[6],nn[6],kk[5][100];
int long x1[50002],y1[50002],x[50002],y[50002],nrr,ys[50002];
int long min1=1,max1=-1,max2=-1,min2=1;
ofstream gg("test.out");
/*void afiseaza_vect(int long v[100],int long n)
{int i;
for(i=1;i<=n;i++)
gg<<v[i]<<" ";
gg<<'\n';
}*/
void citire()
{int long n,i,xs,ys,a,b;
ifstream f("pachete.in");
f>>n>>xs>>ys;
for(i=1;i<=n;i++)
{f>>a>>b;
a-=xs;b-=ys;
/*if(a==0&&b!=0)
{if(b>0)
kk[1][++nn[1]]=b;
else
kk[2][++nn[2]]=b*(-1);
}
if(b==0&&a!=0)
{if(a>0)
kk[3][++nn[3]]=a;
else
kk[4][++nn[4]]=a*(-1);
} */
if(a>=0&&b>=0)
{cadr[1][0][++nr[1]]=a;
cadr[1][1][nr[1]]=b;
}
if(a>=0&&b<0)
{cadr[4][0][++nr[4]]=a;
cadr[4][1][nr[4]]=b*(-1);
}
if(a<0&&b<=0)
{cadr[3][0][++nr[3]]=a*(-1);
cadr[3][1][nr[3]]=b*(-1);
}
if(a<0&&b>0)
{cadr[2][0][++nr[2]]=a*(-1);
cadr[2][1][nr[2]]=b;
}
}
}
int long cautare(int long y)
{int long i,d,min=y+1;
for(i=0;i<=nrr;i++)
if(y-ys[i]<min&&y-ys[i]>=0)
d=i;
return d;
}
void merge_sort(int long l, int long r)
{
int long m = (l + r) >> 1, i, j, k;
if (l == r) return;
merge_sort(l, m);
merge_sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m &&x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j]))) //A[i] < A[j]))
{//B[k++] = A[i++];
y1[k]=y[i];
x1[k++]=x[i++];
}
else
{//B[k++] = A[j++];
y1[k]=y[j];
x1[k++]=x[j++];
}
for (k = l; k <= r; k++)
{x[k]=x1[k];
y[k]=y1[k];
}
//A[k] = B[k];
}
int long rezolva(int long n)
{nrr=0;
int long i,c;
memset(y1,0,sizeof(y1));
memset(x1,0,sizeof(x1));
if(n)
merge_sort(1,n);
//afiseaza_vect(x,n);
//afiseaza_vect(y,n);
for(i=1;i<=n;i++)
{c=cautare(y[i]);
if(!c)
ys[++nrr]=y[i];
if(c)
ys[c]=y[i];
}
return nrr;
}
int main()
{int long i,sol=0,j;
citire();
for(i=1;i<=4;i++)
{for(j=1;j<=nr[i];j++)
{x[j]=cadr[i][0][j];
y[j]=cadr[i][1][j];
}
sol+=rezolva(nr[i]);
}
ofstream g("pachete.out");
g<<sol-1;
g.close();
return 0;
}