Pagini recente » Cod sursa (job #930336) | Cod sursa (job #708467) | Cod sursa (job #764615) | Cod sursa (job #1634228) | Cod sursa (job #1361436)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#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 ){
if ( ( B.second - ImportantPoint.second ) * ( A.first - ImportantPoint.first ) > ( B.first - ImportantPoint.first) * ( A.second - ImportantPoint.second) )
return true ;
else
return false;
}
double 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[1] , Points[Pointu] );
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[K]] , Points[i] ) < 0 )
--K;
stack[++K] = i ;
}
cout << K << "\n" ;
cout << fixed << setprecision(6);
for ( i = 1 ; i <= K ; ++i )
cout << Points[stack[i]].first << " " << Points[stack[i]].second << "\n";
in.close();
out.close();
return 0;
}