#include #include #define MaxSize 200 #define ShowSort typedef struct { int x, y; } POINT; POINT p[ MaxSize ]; int N; void read_points( void ); int cmp_sort( const void *, const void * ); int cmp_graham( POINT, POINT, POINT ); void dump_points( int ); int graham_scan( void ); int cross( POINT, POINT, POINT ); main() { int M; read_points(); M = graham_scan(); dump_points( M ); return EXIT_SUCCESS; } void read_points( void ) { int xval, yval; N = 0; while ( scanf( "%d%d", &xval, &yval ) != EOF ) { N++; p[ N ].x = xval; p[ N ].y = yval; } } int cmp_sort( const void *ptr1, const void *ptr2 ) { int delta_x1, delta_x2, delta_y1, delta_y2, distsq1, distsq2, cr; POINT p0, p1, p2; p0 = p[ 1 ]; p1 = *( ( POINT * ) ptr1 ); p2 = *( ( POINT * ) ptr2 ); if ( p1.x == p2.x && p1.y == p2.y ) return 0; if ( ( cr = cross( p0, p1, p2 ) ) != 0 ) return -cr; delta_x1 = p1.x - p0.x; delta_x2 = p2.x - p0.x; delta_y1 = p1.y - p0.y; delta_y2 = p2.y - p0.y; distsq1 = delta_x1 * delta_x1 + delta_y1 * delta_y1; distsq2 = delta_x2 * delta_x2 + delta_y2 * delta_y2; return distsq1 - distsq2; } void dump_points( int k ) { int i; printf( "\n\nDumping points\n" ); for ( i = 1; i <= k; i++ ) printf( "\tpoint %3d: %5d%5d\n", i, p[ i ].x, p[ i ].y ); } int graham_scan( void ) { POINT temp; int min, i, M; min = 1; for ( i = 2; i <= N; i++ ) if ( p[ i ].y < p[ min ].y ) min = i; for ( i = 1; i <= N; i++ ) if ( p[ i ].y == p[ min ].y && p[ i ].x < p[ min ].x ) min = i; temp = p[ 1 ]; p[ 1 ] = p[ min ]; p[ min ] = temp; qsort( p + 2, N - 1, sizeof( p[ 0 ] ), cmp_sort ); #ifdef ShowSort printf( "After qsort\n" ); dump_points( N ); printf( "After dump_points\n\n" ); #endif p[ 0 ] = p[ N ]; M = 2; for ( i = 3; i <= N; i++ ) { while ( cmp_graham( p[ M ], p[ M - 1 ], p[ i ] ) > 0 ) M--; M++; temp = p[ M ]; p[ M ] = p[ i ]; p[ i ] = temp; } return M; } int cmp_graham( POINT p0, POINT p1, POINT p2 ) { int cr; if ( p1.x == p2.x && p1.y == p2.y ) return 0; if ( ( cr = cross( p0, p1, p2 ) ) != 0 ) return cr; return 1; } int cross( POINT p0, POINT p1, POINT p2 ) { int delta_x1, delta_x2, delta_y1, delta_y2; delta_x1 = p1.x - p0.x; delta_x2 = p2.x - p0.x; delta_y1 = p1.y - p0.y; delta_y2 = p2.y - p0.y; return delta_x1 * delta_y2 - delta_x2 * delta_y1; }