Cod sursa(job #1361365)

Utilizator superman_01Avramescu Cristian superman_01 Data 25 februarie 2015 20:52:52
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>

#define NMAX 120005
#define INF 0x3f3f3f3f
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

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


pair < double , double > Points[NMAX] , ImportantPoint;
int stack[NMAX] , N ,Pointu ;

bool cmp ( pair < double , double > A , pair < double , double > B ){
     return ( B.second - ImportantPoint.second ) * ( A.first - ImportantPoint.first ) > ( B.first - ImportantPoint.first) * ( A.second - ImportantPoint.second) ;
}
bool Area ( pair < double , double > A , pair < double , double > B , pair < double , double > C ){
     return ( B.first - A.first ) *( C.second - A.second) - (C.first - A.first ) * ( B.second -  A.second );
}


int main ( void ){
    int i , j ;
    in >> N ;
    ImportantPoint.first = ImportantPoint.second  = INF;
    for ( i = 1 ; i <= N ; ++i ){
       in >> Points[i].first >> Points[i].second ;
        if ( Points[i].first < ImportantPoint.first or ( Points[i].first == ImportantPoint.first and Points[i].second < ImportantPoint.second ) )
        ImportantPoint = Points[i] , Pointu = i ;
    }
    swap ( Points[Pointu] , Points[1] );
    sort ( Points + 2 , Points + N + 1 , cmp );
    stack[1] = 1 ;
    stack[2] = 2 ;
    int K = 2 ;
    for ( i = 3 ; i <= N ; ++i ){

      while ( K > 1 and Area ( Points[stack[K-1]] , Points[stack[stack[K]]]  , Points[i] ) < 0  )
         --K;
        stack[++K] = i ;
    }
    out << K ;
    out << fixed << setprecision(6);
    for ( i = 1 ; i <= K ; ++i )
    out << Points[stack[i]].first << " " << Points[stack[i]].second << "\n";
    in.close();
    out.close();
    return 0;
}