Cod sursa(job #35651)

Utilizator the_andyAndrei Stefan the_andy Data 22 martie 2007 11:47:12
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.34 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;
long int x0;
long int y0;

struct punct
{
long x;
long y;
};

inline unsigned long mdl(long x)
{
if(x<0) return -x;
  else
  return x;
}

inline int interval(long lx,long ly,long x)
  {
  if(lx<=ly)
    if((x>=lx)&&(x<=ly))
      return 1;
      else
      return 0;
  if(lx>ly)
    if((x>=ly)&&(x<=lx))
      return 1;
      else
      return 0;    
  }

//functie de sortare
inline int sort_manhattan(punct p1,punct p2)
  {
  unsigned long d1;
  unsigned long d2;
  
  d1=mdl(x0-p1.x)+mdl(y0-p1.y);
  d2=mdl(x0-p2.x)+mdl(y0-p2.y);
  
  return (d1<d2);
  }

//functie de semn
inline int sign(unsigned long x)
{
if(x<0) return -1;
if(x>=0) return 1;
};

int main(void)
{
FILE *f;
unsigned int n;
unsigned int i;
unsigned int j;
unsigned long dmax;
unsigned int pmax;
vector< punct > v;
vector< punct >::iterator it;
vector< unsigned int > vt;
unsigned int vd[50000];
unsigned int vtata[50000];
long int drumuri=0;
unsigned int pas;
punct p;
int sx;int sy;

//citeste datele
f=fopen("pachete.in","rt");
fscanf(f,"%d",&n);
fscanf(f,"%ld %ld",&x0,&y0);
for(i=0;i<n;i++)
  {
  fscanf(f,"%ld %ld",&p.x,&p.y);
  v.push_back(p);
  }
fclose(f);

dmax=0;
pmax=50001;

//sorteaza nodurile in ordinea distantei manhattan
stable_sort(v.begin(),v.end(),sort_manhattan);

//cat timp mai sunt puncte de procesat
while(v.size()>0)
  {
  //face un drum nou
  drumuri+=1;

  //afla cel mai indeparat punct de radacina
  pmax=v.size()-1;
      
  //face semnele pe cele 2 axe
  sx=v[pmax].x-x0;
  sy=v[pmax].y-y0;
  
  //pune intr-un vector temporar doar nodurile din dreptunghiul
  //format de radacina cu pmax
  vt.clear();
  for(i=0;i<v.size();i++)
    if(interval(x0,v[pmax].x,v[i].x)&&interval(y0,v[pmax].y,v[i].y))
      vt.push_back(i);
  
  //afiseaza vt
//   cout<<"vt:";
//   for(i=0;i<vt.size();i++)
//   cout<<vt[i]<<"|";
//   cin>>i;  
  
  //afla numarul maxim de noduri ce poate fi pus pe drumul dintre radacina si pmin
  //complexitate n patrat
  for(i=0;i<vt.size();i++)
    vd[i]=0;
  vd[0]=1;
  vtata[0]=50001;
  for(i=1;i<vt.size();i++)
     {
     vd[i]=1; //distanta de la el direct la radacina
     vtata[i]=50001;
     for(j=0;j<i;j++) //ia toate nodurie dinaintea lui
         //vede daca nodul j se afla inaintea lui i geometric
         if((sign(v[i].x-v[j].x)==sign(sx))&&(sign(v[i].y-v[j].y)==sign(sy)))
           {
           vd[i]=vd[j]+1;
           vtata[i]=j;
           }
           
     }
  
  //afiseaza vd
//  cout<<"vd:";
//  for(i=0;i<vt.size();i++)
//    cout<<vd[i]<<"|";
//  cout<<endl<<"vtata:";
//  for(i=0;i<vt.size();i++)
//    cout<<vtata[i]<<"|";
//  cin>>i;  
  
  //sterge nodurile care au fost selectate
  j=vt.size()-1;
  pas=0;
  while(j!=50001)
    {
    //sterge nodul j
    it=v.begin();
    it+=vt[j]-pas;
    v.erase(it);
//    cout<<"-------";
//    cout<<"j="<<vt[j]<<endl;
//    cout<<(*it).x<<" "<<(*it).y<<"|";
//    cout<<endl;
//    for(i=0;i<v.size();i++)
//      cout<<v[i].x<<" "<<v[i].y<<"|";

//    cin>>i;
    pas+=1;        
    j=vtata[j];
//    cout<<"Jnou="<<j<<endl;
    }
  }

//afiseaza solutia
f=fopen("pachete.out","wt");
fprintf(f,"%ld\n",drumuri);
fclose(f);


//sf
return 0;
};