Cod sursa(job #2334891)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 3 februarie 2019 12:16:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

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

const int NMAX = 120005;

int N;
struct p
{
  double x, y;
  double tg;
} A[NMAX];

void Read()
{
  fin >> N;

  for( int i = 1; i <= N; ++i )
  {
    fin >> A[i].x >> A[i].y;
  }

  fin.close();
}

bool comp1( p A, p B )
{
  return A.y <= B.y || ( A.y == B.y && A.x < B.x );
}

bool comp2( p A, p B )
{
  return A.tg <= B.tg;
}

int Orientation( p A, p B, p C )   ///  1 - clockwise;  2 - coliniar  3 - counterclock
{
  double aux;

  aux = ( B.y - A.y ) * ( C.x - B.x ) - ( C.y - B.y ) * ( B.x - A.x );

  if( aux < 0 ) return 3;
  if( aux == 0 ) return 2;
  if( aux > 0 ) return 1;
}

void Do()
{
  vector <p> lf;
  vector <p> up;
  vector <p> rg;

  sort( &A[1], &A[N + 1], comp1 );

  for( int i = 2; i <= N; ++i )
    if( A[i].x == A[1].x ) up.push_back( A[i] );
    else
      {
        A[i].tg = ( double )( A[i].y - A[1].y ) / ( A[i].x - A[1].x );

        if( A[i].x > A[1].x ) rg.push_back( A[i] );
        else lf.push_back( A[i] );
      }

  sort( rg.begin(), rg.end(), comp2 );
  sort( lf.begin(), lf.end(), comp2 );

  vector <p> points;
  for( int i = 0; i < rg.size(); ++i )
    points.push_back( rg[i] );
  for( int i = 0; i < up.size(); ++i )
    points.push_back( up[i] );
  for( int i = 0; i < lf.size(); ++i )
    points.push_back( lf[i] );

  vector <p> S;

  S.push_back( A[1] );
  S.push_back( points[0] );
  S.push_back( points[1] );

  for( int i = 2; i < points.size(); ++i )
  {
    while( Orientation( S[ S.size() - 2 ], S[ S.size() - 1 ], points[i] ) != 3 )
      S.pop_back();

    S.push_back( points[i] );
  }

  fout << S.size() << '\n';

  for( int i = 0; i < S.size(); ++i )
    fout << fixed << setprecision( 8 ) << S[i].x << ' ' << S[i].y << '\n';
}

int main()
{
    Read();
    Do();

    return 0;
}