/* 
   Written by Joseph O'Rourke.
   Graham's algorithm for hull of 2-dim points.
   See "Computational Geometry in C."
*/
#include	<stdio.h>
#include	<math.h>
#include	<stdlib.h>
/* #include	<malloc.h> */

#define	ERROR	1
#define	X	0
#define	Y	1
typedef	enum { FALSE, TRUE }	bool;

#define DIM     2               /* Dimension of points */
typedef int     tPointi[DIM];   /* type integer point */
typedef double  tPointd[DIM];   /* type double point */
#define PMAX    100000            /* Max # of pts in polygon */
   
typedef tPointi tPolygoni[PMAX];/* type integer polygon */

typedef	struct tCell *tStack;
struct tCell {
	int	i;
	tStack	next;
};

tStack	Pop( tStack p );
tStack	Push( tStack t, tStack p );
tStack	GetCell( void );
void	PrintStack( tStack t );
tStack	GetPush( int i, tStack t );
tStack	Graham( tPolygoni P );

/*----------from tri.c-------------*/
int     Area2( tPointi a, tPointi b, tPointi c );
bool 	xor( bool x, bool y );
bool    Left( tPointi a, tPointi b, tPointi c );
bool    LeftOn( tPointi a, tPointi b, tPointi c );
void	SubVec( tPointi a, tPointi b, tPointi c );
int     Dot( tPointi a, tPointi b );
int     Length2( tPointi p );
void	PointAssign( tPointi a, tPointi b );
int	ReadPoly( tPolygoni P );
void	PrintPoly( int n, tPolygoni P );
void	PrintPoint( tPointi p );
/*----------from tri.c-------------*/
int	Compare( tPointi *p1, tPointi *p2 );
void	FindLowest( int n, tPolygoni P );

static	tPolygoni	P;	/* global so compare can access it. */
int	n;
main()
{
	tStack	top;

	n = ReadPoly( P );
	FindLowest( n, P );
    /*
	PrintPoly( n, P );
    */
	qsort(
		(void *) P[1],		/* base: pointer to 1st elem */
		n-1,			/* count: # of elems */
		sizeof( tPointi ),	/* size of each elem */
		Compare			/* -1,0,+1 compare fnc */
	);
    /*
	PrintPoly( n, P );
    */

	top = NULL;
	top = Graham( P );
    /*
	printf("Hull:\n");
    */
	PrintStack( top );
}

/*
	FindLowest finds the rightmost lowest point and swaps with 0-th.
	The lowest point has the min y-coord, and amongst those, the
	max x-coord: so it is rightmost among the lowest.
*/
void	FindLowest( int n, tPolygoni P )
{
	int 	i;
	int	m;	/* Index of lowest so far. */
	tPointi	low;	/* To hold point when swapping. */

	m = 0;
	for ( i = 1; i < n; i++ )
		if ( (P[i][Y] < P[m][Y]) ||
		    ((P[i][Y] == P[m][Y]) && (P[i][X] > P[m][X])) ) 
			m = i;
	/* swap */
	PointAssign( low, P[m] );
	PointAssign( P[m], P[0] );
	PointAssign( P[0], low  );
}
/*
	Compare: returns -1,0,+1 if p1 < p2, =, or > respectively;
	here "<" means smaller angle.  Follows the conventions of qsort.
*/
int	Compare( tPointi *p1, tPointi *p2 )
{
	int 	a;		/* area */
	tPointi	r1, r2;		/* ri = pi - p0 */
	int	len1, len2;	/* length of r1 & r2 */

	a = Area2( P[0], *p1, *p2 );
	if (a > 0)
		return -1;
	else if (a < 0)
		return 1;
	else {
		SubVec( *p1, P[0], r1 );
		SubVec( *p2, P[0], r2 );
		len1 = Length2( r1 );
		len2 = Length2( r2 );
        /*
		printf("compare:\n");
		PrintPoint(r1);PrintPoint(r2);
		printf("\nlen1=%d, len2=%d\n", len1, len2);
        */
		return (len1 < len2) ? -1 : (len1 > len2) ? 1 : 0;
	}
}

#include	"stack.c"
/*
	Get a cell, fill it with i, and push it onto the stack.
	Return pointer to stack top.
*/
tStack	GetPush( int i, tStack top )
{
	tStack	p;

	p = GetCell();
	p->i = i;
	return Push( top, p );
}

/*
	Performs the Graham scan on an array of angularly sorted points P.
*/
tStack	Graham( tPolygoni P )
{
	int	i;
	tStack	top;

	/* Initialize stack to (P[n-1], P[0]). */
	top = NULL;
	top = GetPush ( n-1, top );
	top = GetPush ( 0, top );

	/* Bottom two elements will never be removed. */
	i = 1;

	while ( i < n ) {
        /*
		printf("Stack at top of while loop, i=%d:\n", i);
		PrintStack( top );
        */
		if ( Left( P[ (top->next)->i ], P[ top->i ], P[ i ] ) ) {
			top = GetPush ( i, top );
			i++;
		}
		else 	top = Pop( top );
        /*
		printf("Stack at bot of while loop, i=%d:\n", i);
		PrintStack( top );
		putchar('\n');
        */
	}

	/* P[n-1] pushed twice, so pop it off. */
	return	Pop(top);

}

#include	"vector.c"