Cod sursa(job #481938)

Utilizator wefgefAndrei Grigorean wefgef Data 1 septembrie 2010 23:42:42
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iomanip>

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();
  
  fout << stiva.size() << "\n";

  for( int i = 0; i < stiva.size(); i++ )
  {
    fout << setprecision(6) << stiva[i].x << " " << stiva[i].y << "\n";
  }

  return 0;
}