Pagini recente » Cod sursa (job #2012506) | Arhiva de probleme | Cod sursa (job #289989) | Clasament preoni53b | Cod sursa (job #6985)
Cod sursa(job #6985)
/*
*
*
Info-Arena, preONI 2007, Runda I - Pachete
*
*
*/
#include<stdio.h>
#define INPUT "pachete.in"
#define OUTPUT "pachete.out"
FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");
long n,xinit,yinit,mij;
struct plan{
long x[50000],y[50000];
}plan;
void citire();
void quick(long st, long dr);
void quick2(long st, long dr);
void rezolvare();
int main()
{
long i;
citire();
quick(1,n);
for(i=1;i<=n&&plan.x[i]<xinit;++i);
mij=i;
if(mij>1)
quick2(1,mij-1);
if(mij<n)
quick2(mij,n);
rezolvare();
fclose(fin);
fclose(fout);
return 0;
}
void citire()
{
fscanf(fin, "%ld", &n);
fscanf(fin, "%ld %ld", &xinit, &yinit);
for(long i=1;i<=n;++i)
fscanf(fin, "%ld %ld", &plan.x[i], &plan.y[i]);
}
void quick(long st, long dr)
{
long l=st,m=dr;
while(l!=m)
{
if((plan.x[l]<plan.x[m]&&l>m)||(plan.x[l]>plan.x[m]&&l<m))
{
plan.x[l]=plan.x[l]+plan.x[m];
plan.x[m]=plan.x[l]-plan.x[m];
plan.x[l]=plan.x[l]-plan.x[m];
plan.y[l]=plan.y[l]+plan.y[m];
plan.y[m]=plan.y[l]-plan.y[m];
plan.y[l]=plan.y[l]-plan.y[m];
l=l+m;
m=l-m;
l=l-m;
if(l<m)
--m;
else
++m;
}
else
if(l<m)
--m;
else
++m;
}
if(st!=m) quick(st,m-1);
if(dr!=m) quick(m+1,dr);
}
void quick2(long st, long dr)
{
long l=st,m=dr;
while(l!=m)
{
if(((plan.y[l]<plan.y[m]&&l>m)||(plan.y[l]>plan.y[m]&&l<m))&&(plan.x[l]==plan.x[m]))
{
plan.x[l]=plan.x[l]+plan.x[m];
plan.x[m]=plan.x[l]-plan.x[m];
plan.x[l]=plan.x[l]-plan.x[m];
plan.y[l]=plan.y[l]+plan.y[m];
plan.y[m]=plan.y[l]-plan.y[m];
plan.y[l]=plan.y[l]-plan.y[m];
l=l+m;
m=l-m;
l=l-m;
if(l<m)
--m;
else
++m;
}
else
if(l<m)
--m;
else
++m;
}
if(st!=m) quick2(st,m-1);
if(dr!=m) quick2(m+1,dr);
}
void quick3(long st, long dr)
{
long l=st,m=dr;
while(l!=m)
{
if(((plan.y[l]<plan.y[m]&&l<m)||(plan.y[l]>plan.y[m]&&l>m))&&(plan.x[l]==plan.x[m]))
{
plan.x[l]=plan.x[l]+plan.x[m];
plan.x[m]=plan.x[l]-plan.x[m];
plan.x[l]=plan.x[l]-plan.x[m];
plan.y[l]=plan.y[l]+plan.y[m];
plan.y[m]=plan.y[l]-plan.y[m];
plan.y[l]=plan.y[l]-plan.y[m];
l=l+m;
m=l-m;
l=l-m;
if(l<m)
--m;
else
++m;
}
else
if(l<m)
--m;
else
++m;
}
if(st!=m) quick3(st,m-1);
if(dr!=m) quick3(m+1,dr);
}
void rezolvare()
{
long long k=0,l=0,i,min1,min2,pas,temp=0;
min1=yinit;
min2=yinit;
pas=0;
for(i=mij;i<=n;++i)
{
temp=plan.y[i];
if(plan.y[i]>=yinit)
{
if(pas==0)
{
++k;
pas=3;
}
else
if(pas==4)
{
++k;
pas=5;
}
if(plan.y[i]<min1)
++k;
min1=plan.y[i];
}
else
{
if(pas==0)
{
++k;
pas=4;
}
else
if(pas==3)
{
++k;
pas=5;
}
if(plan.y[i]>min2)
++k;
min2=plan.y[i];
}
}
min1=yinit;
min2=yinit;
pas=0;
for(i=mij-1;i>=1;--i)
{
temp=plan.y[i];
if(plan.y[i]>=yinit)
{
if(pas==0)
{
++l;
pas=3;
}
else
if(pas==4)
{
++l;
pas=5;
}
if(plan.y[i]<min1)
++l;
min1=plan.y[i];
}
else
{
if(pas==0)
{
++l;
pas=4;
}
else
if(pas==3)
{
++l;
pas=5;
}
if(plan.y[i]>min2)
++l;
min2=plan.y[i];
}
}
fprintf(fout, "%lld\n", l+k);
}