Pagini recente » Cod sursa (job #603496) | Cod sursa (job #703902) | Cod sursa (job #1998094) | Cod sursa (job #1956990) | Cod sursa (job #1826476)
#include <cstdio>
#include <algorithm>
#include <cmath>
const double eps=1.e-12;
int n, h[120005];
struct POINT
{
double x, y;
};
POINT LL, v[120005];
using namespace std;
double cp( POINT P1, POINT P2, POINT P3 )
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw( POINT P1, POINT P2, POINT P3 )
{
double crossp=cp(P1,P2,P3);
if( fabs(crossp)<eps )
return 0;
if( crossp>=eps )
return 1;
return -1;
}
bool cmp( POINT A, POINT B )
{
int c=ccw(LL,A,B);
if( c==1 )
return 1;
if( c==-1 )
return 0;
}
void afis( int k )
{
int i;
printf( "%d\n", k );
for( i=1;i<=k;i++ )
printf( "%lf %lf\n", v[h[i]].x, v[h[i]].y );
}
void infasuratoare( )
{
int top=1, i=2;
h[0]=0;
h[1]=1;
while( i<=n )
{
if( ccw(v[h[top-1]],v[h[top]],v[i])>0 )
{
h[++top]=i;
i++;
}
else
top--;
}
afis(top);
}
int main()
{
freopen( "infasuratoare.in", "r", stdin );
freopen( "infasuratoare.out", "w", stdout );
int i;
scanf( "%d", &n );
for( i=1;i<=n;i++ )
{
scanf( "%lf %lf", &v[i].x, &v[i].y );
if( v[0].y-v[i].y>0 )
{
v[0].y=v[i].y;
v[0].x=v[i].x;
}
else
if( fabs(v[0].y-v[i].y)<eps && v[0].x-v[i].x>=eps )
v[0].x=v[i].x;
}
LL.x=v[0].x;
LL.y=v[0].y;
sort(v+1,v+n+1,cmp);
infasuratoare();
return 0;
}