Pagini recente » Cod sursa (job #2445961) | Cod sursa (job #2661292) | Cod sursa (job #1953849) | Cod sursa (job #2693185) | Cod sursa (job #1816643)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define N 120010
#define e 0.000000000001
using namespace std;
struct point {
double x , y ;
};
point v [ N ], stk [ N ];
int stp;
int 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[stp], 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 < 0 || stp == -1 ){
stp = i;
}
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 >=2 && sgn ( stk [sp-1] , stk[sp] , v[i]) < 0 ){
sp--;
}
stk[++sp] = v[i];
}
printf("%d\n",sp+1);
for ( i = 0 ; i <= sp ; i++ ){
printf("%lf %lf\n",stk[i].x , stk[i].y );
}
return 0;
}