Pagini recente » Cod sursa (job #3040177) | Cod sursa (job #3223941) | Cod sursa (job #2392653) | Cod sursa (job #7281) | Cod sursa (job #1064660)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int Nmax = 120001;
struct Point
{
double x;
double y;
bool operator < ( const Point &A ) const
{
if ( x == A.x )
return y < A.y;
else
return x < A.x;
}
};
Point points[Nmax];
Point stiva[Nmax];
int N, head;
double Cross_Product( Point A, Point B, Point C )
{
return ( B.x - A.x ) * ( C.y - A.y ) -
( B.y - A.y ) * ( C.x - A.x );
}
int cmp( Point A, Point B )
{
return ( Cross_Product( points[1], A, B ) < 0 );
}
void SortPoints()
{
for ( int i = 2; i <= N; ++i )
{
if ( points[1] < points[i] )
swap( points[1], points[i] );
}
sort( points + 2, points + N + 1, cmp );
}
void GrahamScan()
{
stiva[ ++head ] = points[1];
stiva[ ++head ] = points[2];
for ( int i = 3; i <= N; ++i )
{
while ( head >= 2 && Cross_Product( stiva[head - 1], stiva[head], points[i] ) > 0 )
head--;
stiva[ ++head ] = points[i];
}
}
void read()
{
ifstream f("infasuratoare.in");
f >> N;
for ( int i = 1; i <= N; ++i )
{
f >> points[i].x >> points[i].y;
}
}
void print()
{
ofstream g("infasuratoare.out");
g << head << "\n";
for ( int i = head; i >= 1; i-- )
{
g << fixed << setprecision( 10 );
g << stiva[i].x << " " << stiva[i].y << "\n";
}
}
int main()
{
read();
SortPoints();
GrahamScan();
print();
return 0;
}