Cod sursa(job #2371366)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 6 martie 2019 17:21:58
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMAX = 120010;

int N;

struct punct
{
  double x, y;
} A[NMAX];

vector <int> S;

void Read()
{
  fin >> N;

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

  fin.close();
}

int Orientare( punct A, punct B, punct C )
{
  int res = ( B.y - A.y ) * ( C.x - B.x ) - ( B.x - A.x ) * ( C.y - B.y );

  if( res < 0 ) return 1;
  if( res == 0 ) return 0;
  if( res > 0 ) return -1;
}

bool comp( punct B, punct C )
{
  return ( Orientare( A[1], B, C ) >= 0 );
}

void Do()
{
  int lowest;
  double x_min = 2000000000, y_min = 2000000000;

  for( int i = 1; i <= N; ++i )
   if( A[i].y < y_min || ( A[i].y == y_min && A[i].x < x_min ) )
   {
     lowest = i;
     x_min = A[i].x;
     y_min = A[i].y;
   }

   swap( A[1], A[lowest] );

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

   S.push_back( 1 );
   S.push_back( 2 );
   S.push_back( 3 );

   for( int i = 4; i <= N; ++i )
   {
     while( Orientare( A[ S[ S.size() - 2 ]], A[ S.back() ], A[i] ) < 0 )
      S.pop_back();

     S.push_back( i );
   }

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

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

   fout.close();
}

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

    return 0;
}