Cod sursa(job #2371431)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 6 martie 2019 17:36:19
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 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 )
{
  return ( 1LL * B.y - A.y ) * ( 1LL * C.x - B.x ) <= ( 1LL * B.x - A.x ) * ( 1LL * C.y - B.y );
}

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

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] ) )
      S.pop_back();

     S.push_back( i );
   }

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

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

   fout.close();
}

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

    return 0;
}