Pagini recente » Cod sursa (job #1179717) | Cod sursa (job #1078129) | Cod sursa (job #1638829) | Cod sursa (job #1275998) | Cod sursa (job #1817646)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define N 120110
#define e 0.000000000001
using namespace std;
struct point {
double x , y ;
};
point v [ N ], stk [ N ];
int stp =-1 ;
double sgn ( 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 sgn ( v[0], a ,b ) < 0;
}
double absd( double x ){
if ( x < 0 ){
return -x;
}
return x ;
}
int main(){
int n ,i ;
point t;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i = 0 ; i < n ; i++ ){
scanf("%lf %lf",&v[i].x , & v[i].y );
}
for (i = 0 ; i < n ; i++ ){
if ( v[i].y < v[stp].y || stp == -1 ){
stp = i;
}else if ( absd (v[i].y - v[stp].y ) < e ){
if( v[ i ].x - v[ stp ].x < 0 ){
stp = i;
}
}
}
t = v [ stp ] ;
v [ stp ] = v[ 0 ];
v[ 0 ] = t ;
sort( v +1 , v + n , cmp );
stk [ 0 ] = v[ 0 ];
stk [ 1 ] = v[ 1 ];
int sp = 1;
for ( i = 2 ; i <n ; i++ ){
while ( sp >=1 && sgn ( stk [sp-1] , stk[sp] , v[i]) > 0 ){
sp--;
}
stk[++sp] = v[i];
}
printf("%d\n",sp+1);
for ( i = sp ; i >=0 ; i-- ){
printf("%lf %lf\n",stk[i].x , stk[i].y );
}
return 0;
}