Cod sursa(job #163660)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 22 martie 2008 14:52:33
Problema Wanted Scor 10
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 1.63 kb
#include <fstream>
std::ifstream f1("wanted.in");
std::ofstream f2("wanted.out");
struct elem{
             int x, y;
           }orase[210];
long dist;
int n, poz, i;

void qsort(int jos, int sus);
void rez(int p, int u, int poz);
int pivot(int jos, int sus);

int main()
{
  f1>>n;
  for (i=0; i<n; i++)
    f1>>orase[i].x>>orase[i].y;
  qsort(0, n-1);
//  if (((n-1)%2)==0)
//    poz=(n-1)/2;
//  else
 // {
//    poz=(n-1)/2;
//    if (abs(orase[poz].x)>abs(orase[poz+1].x))
//      poz++;
//  }//else
//  dist=abs(orase[poz].x)+abs(orase[poz].y); 
  poz=n;
  rez(0, n-1, poz);
  f2<<dist;
  return 0;
}//main

void rez(int p, int u, int poz)
{
  int t;
  if (p==u)
  {
    dist+=abs(orase[poz].y)+abs(orase[p].x-orase[poz].x)+abs(orase[p].y);
    poz=p;
  }//if
  else
  { 
    if (((p+u)%2)==0)
      t=(p+u)/2;
    else
    {
      t=(p+u)/2;
      if (abs(orase[t].x)>abs(orase[t+1].x))
        t++;
    }//else
    dist+=abs(orase[poz].y)+abs(orase[t].x-orase[poz].x)+abs(orase[t].y);
    poz=t;
    if ((poz-p)>(u-poz))
      rez(p, poz-1, poz);
    else
      rez(poz+1, u, poz); 
  }//else 
}//rez

int pivot(int jos, int sus)
{
  int i1=jos, i2=sus;
  elem t;
  while (i1<i2)
  {
    while ((orase[i1].x<=orase[jos].x)&&(i1<=i2))
      i1++;
    while ((orase[i2].x>orase[jos].x)&&(i1<=i2))
      i2--;
    if ((orase[i1].x>orase[i2].x)&&(i1<i2))
    {
      t=orase[i1];
      orase[i1]=orase[i2];
      orase[i2]=t;
    }//if
  }//while
  t=orase[i2];
  orase[i2]=orase[jos];
  orase[jos]=t;  
  return i2;
}//pivot

void qsort(int jos, int sus)
{
  int p;
  if (jos<sus)
  {
    p=pivot(jos, sus);
    qsort(jos, p-1);
    qsort(p+1, sus);
  }//if
}//qsort