Pagini recente » Cod sursa (job #478923) | Cod sursa (job #3291815) | Cod sursa (job #2885097) | Cod sursa (job #2765935) | Cod sursa (job #1504572)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream is("infasuratoare.in");
ofstream os("infasuratoare.out");
#define x second
#define y first
int n, top;
typedef pair<double, double> Pct;
#define MAX_N 120005
Pct v[MAX_N];
Pct stk[MAX_N];
void Read();
void ConvexHull();
void Write();
void SortPct();
inline double Cmp( const Pct& p1, const Pct& p2 );
inline double CrossProduct( const Pct& A, const Pct& B, const Pct& C );
int main()
{
Read();
ConvexHull();
Write();
is.close();
os.close();
return 0;
}
void Read()
{
is >> n;
for ( int i = 1; i <= n; i++ )
is >> v[i].x >> v[i].y;
}
void ConvexHull()
{
SortPct();
stk[1] = v[1];
stk[2] = v[2];
top = 2;
for( int i = 3; i <= n; i++ )
{
while( top >= 2 && CrossProduct(stk[top - 1], stk[top], v[i]) < 0 )
top--;
stk[++top] = v[i];
}
}
void SortPct()
{
int pos = 1;
for ( int i = 2; i <= n; i++ )
if ( v[i] < v[pos] )
pos = i;
swap( v[1], v[pos] );
sort( v + 2, v + n + 1, Cmp );
}
inline double Cmp( const Pct& p1, const Pct& p2 )
{
return CrossProduct( v[1], p1, p2 ) > 0;
}
inline double CrossProduct( const Pct& A, const Pct& B, const Pct& C )
{
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}
void Write()
{
os << fixed;
os << top << '\n';
for ( int i = 1; i <= top; i++ )
os << setprecision(6) << stk[i].x << ' ' << stk[i].y << '\n';
}