Pagini recente » Cod sursa (job #1559026) | Cod sursa (job #323472) | Cod sursa (job #792061) | Cod sursa (job #2999913) | Cod sursa (job #3216267)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct point
{
double x, y;
}v[200005];
int n ;
long double cross_product(point a , point b , point c )
{
return ( b.x-a.x) * ( c.y-a.y) - ( c.x - a . x ) * ( b . y - a.y );
}
bool cmp(point a , point b )
{
return (cross_product(v[1],a,b) < 0 ) ;
}
point stiva[20005];
int main()
{
cin >> n ;
long long ind = 0 ;
long long miny , minx ;
cin >> v[1].x >> v[1].y;
miny = v[1].y;
minx = v[1].x;
for ( int i = 2 ; i <= n ; i ++ )
{
cin >> v[i].x >> v[i].y ;
if ( v[i].x < minx)
{
minx = v[i].x;
miny = v[i].y ;
ind = i ;
}
else
if ( v[i].x == minx )
{
if ( v[i].y < miny)
{
miny = v[i].y;
ind = i ;
}
}
}
swap(v[ind],v[1]);
sort(v+2,v+n+1,cmp);
int head = 1 ;
stiva[head] = v[1];
stiva[head+1] = v[2];
head ++ ;
for( int i = 3 ; i <= n ; i ++ )
{
while ( head >= 2 && cross_product(stiva[head-1],stiva[head],v[i]) > 0 )
{
head -- ;
}
stiva[++head] = v[i];
}
cout << head << '\n';
for ( int i = head ; i >= 1 ; i -- )
{
cout << fixed << setprecision(12) << stiva[i].x << " " << stiva[i].y << '\n';
}
return 0;
}