Cod sursa(job #2572190)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 5 martie 2020 12:02:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 120005;

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

vector <pnct> hull;

bool CounterClock( const pnct & A, const pnct & B, const pnct & C ) {
    return ( B.y - A.y ) * ( C.x - B.x ) < ( B.x - A.x ) * ( C.y - B.y );
}

bool comp( const pnct & A, const pnct & B ) {
    return CounterClock( p[1], A, B );
}

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

void Do()
{
    int _first;
    double xmin, ymin;

    _first = 1;
    xmin = p[1].x; ymin = p[1].y;
    for( int i = 2; i <= N; ++i )
      if( p[i].x < xmin || ( p[i].x == xmin && p[i].y < ymin ) ) {
          _first = i;
          xmin = p[i].x; ymin = p[i].y;
      }

    swap( p[1], p[_first] );
    sort( &p[2], &p[N + 1], comp );

    hull.push_back( p[1] );
    hull.push_back( p[2] );

    for( int i = 3; i <= N; ++i ) {
      while( !CounterClock( hull[ hull.size() - 2 ], hull.back(), p[i] ) )
        hull.pop_back();
      hull.push_back( p[i] );
    }

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

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

    return 0;
}