Cod sursa(job #36180)

Utilizator the_andyAndrei Stefan the_andy Data 23 martie 2007 08:49:13
Problema Pachete Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include<stdio.h>
#include<vector>
#include<algorithm>


using namespace std;

//constanta care determina daca sorteaza invers
int inv=1;

struct punct
{
long x;
long y;
};

inline int comp(punct p1,punct p2)
{
if (inv==0)
  {
  return p1.y<p2.y;
  }
  else
  {
  return p1.y>p2.y;
  }
}


int main(void)
{
FILE *f;
vector< punct > v1;
vector< punct > v2;
vector< punct > v3;
vector< punct > v4;
unsigned int i,j,n;
long int x,y;
long int x0,y0;
punct p;
unsigned int drumuri=0;
vector<bool> s1;
vector<bool> s2;
vector<bool> s3;
vector<bool> s4;
unsigned int n1,n2,n3,n4;

//citeste datele de intrare si separa pe cadrane
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",&x,&y);
  p.x=x;
  p.y=y;
  if((x>x0)&&(y>y0))
    {
    v1.push_back(p);
    s1.push_back(false);
    }
  if((x>x0)&&(y<y0))
    {
    v2.push_back(p);
    s2.push_back(false);
    }
  if((x<x0)&&(y<y0))
    {
    v3.push_back(p);
    s3.push_back(false);
    }
  if((x<x0)&&(y>y0))
    {
    v4.push_back(p);
    s4.push_back(false);
    }
  }
fclose(f);

//sortaeaza punctele in cadran dupa y
//sorteaza pe 1 si 4 cu normal
inv=0;
stable_sort(v1.begin(),v1.end(),comp);
stable_sort(v4.begin(),v4.end(),comp);
inv=1;
stable_sort(v2.begin(),v2.end(),comp);
stable_sort(v3.begin(),v3.end(),comp);

//face numarul de drumuri din fiecare cadran
n1=v1.size();  
n2=v2.size();  
n3=v3.size();  
n4=v4.size();  

//face numarul de drumuri din cadranul 1
while(n1>0)
  {
  i=0;
  while((s1[i]==true)&&(i<v1.size()))
    i++;
  j=i;
  while(i<v1.size())
    {
    if((s1[i]==false)&&(v1[i].x>=v1[j].x))
       {
       s1[i]=true;
       n1-=1;
       j=i;
       }
    i++;
    }
  drumuri+=1;
  }

//face numarul de drumuri din cadranul 2
while(n2>0)
  {
  i=0;
  while((s2[i]==true)&&(i<v2.size()))
    i++;
  j=i;
  while(i<v2.size())
    {
    if((s2[i]==false)&&(v2[i].x>=v2[j].x))
       {
       s2[i]=true;
       n2-=1;
       j=i;
       }
    i++;
    }
  drumuri+=1;
  }

//face numarul de drumuri din cadranul 3
while(n3>0)
  {
  i=0;
  while((s3[i]==true)&&(i<v3.size()))
    i++;
  j=i;
  while(i<v3.size())
    {
    if((s3[i]==false)&&(v3[i].x<=v3[j].x))
       {
       s3[i]=true;
       n3-=1;
       j=i;
       }
    i++;
    }
  drumuri+=1;
  }

//face numarul de drumuri din cadranul 3
while(n4>0)
  {
  i=0;
  while((s4[i]==true)&&(i<v4.size()))
    i++;
  j=i;
  while(i<v4.size())
    {
    if((s4[i]==false)&&(v4[i].x<=v4[j].x))
       {
       s4[i]=true;
       n4-=1;
       j=i;
       }
    i++;
    }
  drumuri+=1;
  }

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

//sf
return 0;
};