Pagini recente » Cod sursa (job #1867044) | Istoria paginii runda/simvlad000/clasament | Cod sursa (job #2520091) | Cod sursa (job #829433) | Cod sursa (job #2572583)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120005;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
struct punct
{
double x, y;
};
punct P[NMAX];
punct A, B;
bool ToLeft ( const punct & A, const punct & B, const punct & C )
{
return ( 1LL * B.y - A.y )*( C.x - B.x ) < (1LL* C.y - B.y )*( B.x - A.x );
}
bool comp( const punct & B, const punct & C )
{
return ToLeft( P[1], B, C );
}
void Read()
{
fin >> N;
for( int i = 1; i <= N; ++i )
fin >> P[i].x >> P[i].y;
}
vector < punct > S;
void Solve()
{
int first = 1;
for( int i = 2; i <= N; ++i )
if( P[i].x < P[first].x || (P[i].x == P[first].x && P[i].y < P[first].y ) )
first = i;
swap( P[first], P[1] );
sort ( P+2, P+N+1, comp );
//for( int i = 1; i <= N; ++i )fout << P[i].x << ' ' << P[i].y << '\n';
S.push_back( P[1] );
S.push_back( P[2] );
for( int i = 3; i <= N; ++i )
{
A = S[S.size()-1];
B = S[S.size()-2];
//cout << A.x << ' ' << A.y << ' ' << B.x << ' ' << B.y << ' ' << P[i].x << ' ' << P[i].y << ' ' << ToLeft ( B, A, P[i] ) << '\n';
if( ToLeft ( B, A, P[i] ) == 1 )
S.push_back( P[i] );
else
{
while( ToLeft ( B, A, P[i] ) == 0 && i <= N)
{
S.pop_back();
A = S[S.size()-1];
B = S[S.size()-2];
//cout << A.x << ' ' << A.y << ' ' << B.x << ' ' << B.y << '\n';
++i;
}
i--;
if( i <= N ) S.push_back( P[i] );
}
}
fout << S.size() << '\n';
for( int i = 0; i < S.size() ; ++i )
fout << fixed << setprecision( 6 ) << S[i].x << ' ' << S[i].y << '\n';
}
int main()
{
Read();
Solve();
return 0;
}