Pagini recente » Cod sursa (job #2780041) | Cod sursa (job #20151) | Cod sursa (job #555727) | Cod sursa (job #1826814) | Cod sursa (job #2090891)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
double sarrus( pair<double,double> a, pair<double,double> b, pair<double,double> c )
{
return ( a.x*b.y + b.x*c.y + c.x*a.y ) - ( a.y*b.x + b.y*c.x + c.y*a.x );
}
int n, i, top = 2, ind = top;
double dx, dy;
pair < double, double > v[120005], st[120005];
int main()
{
f>>n;
for ( i = 1; i <= n; i++ )
{
f>>dx>>dy;
v[i] = { dx, dy };
}
sort ( v + 1 , v + n + 1 );
st[1] = v[1];
st[2] = v[2];
for ( i = 3; i <= n; i++ )
{
while ( top >= 2 )
{
if ( sarrus( st[top-1], v[i] , st[top] ) < 0 )
{
top--;
}
else
{
break;
}
}
st[++top] = v[i];
}
ind = top;
for ( i = n-1; i >= 1; i-- )
{
while ( top - ind >= 1 )
{
if ( sarrus( st[top-1], v[i] , st[top] ) < 0 )
{
top--;
}
else
{
break;
}
}
st[++top] = v[i];
}
g<<top-1<<'\n';
for ( i = 1 ; i < top ; i++ )
{
g<<setprecision(6) << fixed << st[i].x << " "<< st[i].y<<'\n';
}
return 0;
}