Pagini recente » Cod sursa (job #3031008) | Cod sursa (job #1945645) | Cod sursa (job #2801697) | Cod sursa (job #1687572) | Cod sursa (job #2371431)
#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 )
{
return ( 1LL * B.y - A.y ) * ( 1LL * C.x - B.x ) <= ( 1LL * B.x - A.x ) * ( 1LL * C.y - B.y );
}
bool comp( punct B, punct C )
{
return Orientare( A[1], B, C );
}
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] ) )
S.pop_back();
S.push_back( i );
}
fout << S.size() << '\n';
for( int i = 0; i < S.size(); ++i )
fout << fixed << setprecision( 6 ) << A[ S[i] ].x << ' ' << A[ S[i] ].y << '\n';
fout.close();
}
int main()
{
Read();
Do();
return 0;
}