Pagini recente » Cod sursa (job #196552) | Cod sursa (job #2081520) | Cod sursa (job #2069569) | Cod sursa (job #789992) | Cod sursa (job #1456590)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream fin ( "infasuratoare.in" ) ;
ofstream fout ( "infasuratoare.out" ) ;
struct Punct
{
double x,y;
};
Punct pct[120005];
Punct ch[120005];
int n,M;
double cross_Product ( const Punct& A , const Punct& B , const Punct& C )
{
return A.x * ( B.y - C.y ) + B.x * ( C.y - A.y ) + C.x * ( A.y - B.y ) ;
}
int comp ( const Punct& A , const Punct& B )
{
return cross_Product ( pct[1] , A , B ) < 0;
}
void point_sort()
{
int pos = 1; int i ;
for ( i = 2; i <= n; ++ i )
{
if ( pct[i].x == pct[pos].x )
{
if ( pct[i].y < pct[pos].y )
{
pos = i;
}
}
else if ( pct[i].x < pct[pos].x )
{
pos = i;
}
}
swap ( pct[1],pct[pos] );
sort ( pct+2 , pct+n+1 , comp );
}
void convex_hull()
{
point_sort();
M = 2;
ch[1] = pct[1];
ch[2] = pct[2];
int i ;
for ( i = 3; i <= n; ++i )
{
while ( M >= 2 && cross_Product ( ch[M-1] , ch[M] , pct[i] ) > 0 )
-- M ;
ch[++M] = pct[i];
}
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> pct[i].x >> pct[i].y;
convex_hull();
fout << M << "\n";
for(int i = M; i >= 1; i--)
fout << fixed << setprecision(12) << ch[i].x << " " << ch[i].y << "\n";
return 0 ;
}