Cod sursa(job #6985)

Utilizator alecmanAchim Ioan Alexandru alecman Data 21 ianuarie 2007 11:25:48
Problema Pachete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 3.88 kb
/*
 *
 *
   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);
}