Pagini recente » Cod sursa (job #604804) | Cod sursa (job #2886738) | Cod sursa (job #836078) | Cod sursa (job #332524) | Cod sursa (job #2371366)
#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 )
{
int res = ( B.y - A.y ) * ( C.x - B.x ) - ( B.x - A.x ) * ( C.y - B.y );
if( res < 0 ) return 1;
if( res == 0 ) return 0;
if( res > 0 ) return -1;
}
bool comp( punct B, punct C )
{
return ( Orientare( A[1], B, C ) >= 0 );
}
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] ) < 0 )
S.pop_back();
S.push_back( i );
}
fout << S.size() << '\n';
for( int i = 0; i < S.size(); ++i )
fout << fixed << setprecision( 8 ) << A[ S[i] ].x << ' ' << A[ S[i] ].y << '\n';
fout.close();
}
int main()
{
Read();
Do();
return 0;
}