Pagini recente » Cod sursa (job #1434987) | Cod sursa (job #543022) | Cod sursa (job #52275) | Cod sursa (job #2761572) | Cod sursa (job #1671272)
#include <cstdio>
#include <algorithm>
#define eps 0.000000
double X, Y;
struct puncte
{
double x, y;
} p[120001], st[120001];
using namespace std;
bool cmp( puncte a, puncte b )
{
return (a.y-Y)*(b.x-X)>(b.y-Y)*(a.x-X);
}
inline int verif( int i, int j )
{
double a=(st[i].y-st[i-1].y)*(p[j].x-st[i-1].x);
double b=(p[j].y-st[i-1].y)*(st[i].x-st[i-1].x);
return a<b;
}
int main()
{
freopen( "infasuratoare.in", "r", stdin );
freopen( "infasuratoare.out", "w", stdout );
int n, i, j, vf=0;
scanf( "%d", &n );
for( i=1;i<=n;i++ )
{
scanf( "%lf%lf", &p[i].x, &p[i].y );
if( p[i].x<X )
X=p[i].x, Y=p[i].y, j=i;
}
swap(p[1],p[j]);
sort(p+2,p+n+1,cmp);
for( i=1;i<=n;i++ )
{
while( vf>2 && verif(vf,i) )
vf--;
st[++vf]=p[i];
}
printf( "%d\n", vf );
for( i=vf;i>=1;i-- )
printf( "%.6lf %.6lf\n", st[i].x, st[i].y );
return 0;
}