Cod sursa(job #481939)

Utilizator wefgefAndrei Grigorean wefgef Data 1 septembrie 2010 23:45:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

struct point
{
  double x;
  double y;
};

bool comparison( const point& A, const point& B )
{
  if( A.x < B.x || ( A.x == B.x && A.y < B.y ) )
    return true;
  else
    return false;
}

bool turnsRight( const point& A, const point& B, const point& C )
{
  double a = A.y - B.y;
  double b = B.x - A.x;
  double c = A.x * B.y - B.x * A.y;

  double ecuation = a * C.x + b * C.y + c;
  
  return ( ecuation < 0 );
}

int main()
{
  ifstream fin("infasuratoare.in");
  ofstream fout("infasuratoare.out");

  vector<point> puncte;
  vector<point>::iterator iter;
  int n;

  fin >> n;

  for( int i = 0; i < n; i++ )
  {
    point punct;
    fin >> punct.x >> punct.y;

    puncte.push_back( punct );
  }
  fin.close();

  sort( puncte.begin(), puncte.end(), comparison );

  vector<point> stiva;

  stiva.push_back( puncte[0] );
  stiva.push_back( puncte[1] );

  for( int i = 2; i < puncte.size(); i++ )
  {
    while( stiva.size() > 1 && turnsRight( stiva[stiva.size() - 2], stiva[stiva.size() - 1], puncte[i] ))
      stiva.pop_back();

    stiva.push_back( puncte[i] );
  }

  for( int i = puncte.size() - 2; i >= 0 ; i-- )
  {
    while( stiva.size() > 1 && turnsRight( stiva[stiva.size() - 2], stiva[stiva.size() - 1], puncte[i] ))
      stiva.pop_back();

    stiva.push_back( puncte[i] );
  }

  stiva.pop_back();
  
  freopen("infasuratoare.out", "w", stdout);
  printf("%d\n", stiva.size());
  for( int i = 0; i < stiva.size(); i++ )
  {
    printf("%lf %lf\n", stiva[i].x, stiva[i].y );
  }

  return 0;
}