Pagini recente » Cod sursa (job #2644491) | Cod sursa (job #2512277) | Cod sursa (job #1240681) | Cod sursa (job #2264272) | Cod sursa (job #2572190)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
const int NMAX = 120005;
int N;
struct pnct
{
double x, y;
} p[NMAX];
vector <pnct> hull;
bool CounterClock( const pnct & A, const pnct & B, const pnct & C ) {
return ( B.y - A.y ) * ( C.x - B.x ) < ( B.x - A.x ) * ( C.y - B.y );
}
bool comp( const pnct & A, const pnct & B ) {
return CounterClock( p[1], A, B );
}
void Read() {
fin >> N;
for( int i = 1; i <= N; ++i )
fin >> p[i].x >> p[i].y;
}
void Do()
{
int _first;
double xmin, ymin;
_first = 1;
xmin = p[1].x; ymin = p[1].y;
for( int i = 2; i <= N; ++i )
if( p[i].x < xmin || ( p[i].x == xmin && p[i].y < ymin ) ) {
_first = i;
xmin = p[i].x; ymin = p[i].y;
}
swap( p[1], p[_first] );
sort( &p[2], &p[N + 1], comp );
hull.push_back( p[1] );
hull.push_back( p[2] );
for( int i = 3; i <= N; ++i ) {
while( !CounterClock( hull[ hull.size() - 2 ], hull.back(), p[i] ) )
hull.pop_back();
hull.push_back( p[i] );
}
fout << hull.size() << '\n';
for( int i = 0; i < hull.size(); ++i )
fout << fixed << setprecision( 6 ) << hull[i].x << ' ' << hull[i].y << '\n';
}
int main()
{
Read();
Do();
return 0;
}