Pagini recente » Cod sursa (job #2830179) | Cod sursa (job #477469) | Cod sursa (job #1726340) | Cod sursa (job #1571332) | Cod sursa (job #2334891)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
const int NMAX = 120005;
int N;
struct p
{
double x, y;
double tg;
} A[NMAX];
void Read()
{
fin >> N;
for( int i = 1; i <= N; ++i )
{
fin >> A[i].x >> A[i].y;
}
fin.close();
}
bool comp1( p A, p B )
{
return A.y <= B.y || ( A.y == B.y && A.x < B.x );
}
bool comp2( p A, p B )
{
return A.tg <= B.tg;
}
int Orientation( p A, p B, p C ) /// 1 - clockwise; 2 - coliniar 3 - counterclock
{
double aux;
aux = ( B.y - A.y ) * ( C.x - B.x ) - ( C.y - B.y ) * ( B.x - A.x );
if( aux < 0 ) return 3;
if( aux == 0 ) return 2;
if( aux > 0 ) return 1;
}
void Do()
{
vector <p> lf;
vector <p> up;
vector <p> rg;
sort( &A[1], &A[N + 1], comp1 );
for( int i = 2; i <= N; ++i )
if( A[i].x == A[1].x ) up.push_back( A[i] );
else
{
A[i].tg = ( double )( A[i].y - A[1].y ) / ( A[i].x - A[1].x );
if( A[i].x > A[1].x ) rg.push_back( A[i] );
else lf.push_back( A[i] );
}
sort( rg.begin(), rg.end(), comp2 );
sort( lf.begin(), lf.end(), comp2 );
vector <p> points;
for( int i = 0; i < rg.size(); ++i )
points.push_back( rg[i] );
for( int i = 0; i < up.size(); ++i )
points.push_back( up[i] );
for( int i = 0; i < lf.size(); ++i )
points.push_back( lf[i] );
vector <p> S;
S.push_back( A[1] );
S.push_back( points[0] );
S.push_back( points[1] );
for( int i = 2; i < points.size(); ++i )
{
while( Orientation( S[ S.size() - 2 ], S[ S.size() - 1 ], points[i] ) != 3 )
S.pop_back();
S.push_back( points[i] );
}
fout << S.size() << '\n';
for( int i = 0; i < S.size(); ++i )
fout << fixed << setprecision( 8 ) << S[i].x << ' ' << S[i].y << '\n';
}
int main()
{
Read();
Do();
return 0;
}