Pagini recente » Cod sursa (job #1140585) | Cod sursa (job #1381678) | Cod sursa (job #1425965) | Cod sursa (job #2525153) | Cod sursa (job #1010982)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>
#define NMAX 120005
#define INF 0x3f3f3f3f
using namespace std;
ifstream in ( "infasuratoare.in" );
ofstream out ( "infasuratoare.out" );
pair < double , double > Points[NMAX];
int N;
int stack[NMAX] , k;
pair < double , double > MinPoint;
bool cmp ( pair < double , double > A , pair < double , double > B )
{
if ( ( A.first - MinPoint.first) * (B.second - MinPoint.second) > ( A.second - MinPoint.second ) * ( B.first - MinPoint.first) )
return true ;
else
return false;
}
double SignArea ( 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 ;
in >> N ;
int Ind;
MinPoint.first = MinPoint.second = INF;
for ( i = 1 ; i <= N ; ++i )
{
in >> Points[i].first >> Points[i].second;
if( ( Points[i].second < MinPoint.second ) || ( ( Points[i].second == MinPoint.second ) and ( Points[i].first < MinPoint.first )))
{
MinPoint = Points[i];
Ind = i;
}
}
swap( Points[1] , Points[Ind] );
sort ( Points + 2 , Points + N + 1 , cmp );
stack[1] = 1 ;
stack[2] = 2 ;
k = 2 ;
for ( i = 3 ; i <= N ; ++i )
{
while ( k > 1 and SignArea ( Points[stack[k-1]] , Points[stack[k]] , Points[i] ) < 0)
--k ;
stack[++k] = i ;
}
out << k << "\n";
out << fixed << setprecision(6);
for ( i = 1 ; i <= k ; ++i )
out << Points[stack[i]].first <<" "<< Points[stack[i]].second << "\n";
return 0;
}