import java.util.*;
import java.awt.*;
public class GrahamScanAlgorithm extends GeometryAlgorithm
{
private Point p0;
private Point sorted_p[];
public MyStack S;
void scan ( Point p[] )
{
int N = p.length;
p0 = new Point();
p0 = min_y( p ); //actually, min_y sorts the array such that min y is in p[0]
mergesort (p, 1, N-1);
//sorted_p = p;
sorted_p = new Point[N];
sorted_p[0] = new Point( p0.x, p0.y);
int temp1 = p[1].x;
int temp2 = p[1].y;
sorted_p[1] = new Point( temp1, temp2 ); //load sorted_p[1] with p[1]
N = equal_angles ( N, p );
S = new MyStack();
S.push(sorted_p[N-1]);
S.push(p0);
S.push(sorted_p[1]);
S.push(sorted_p[2]);
for ( int i=3; i<=N; i++ )
{
while ( cross_prod( S.Next_To_Top(), S.Top(), sorted_p[i] ) >= 0 )
S.pop();
S.push( sorted_p[i] );
pause(S);
}
}
private Point min_y (Point p[])
{
int min=0,
N=p.length,
i;
for ( i=1; i<N; i++ )
{
if (p[i].y < p[min].y)
min=i;
else if (p[i].y == p[min].y)
{
if (p[i].x < p[min].x)
min=i;
else if ( p[i].x == p[min].x ) // Delete second min
{
swap ( p, i, N-1 ); // Swap p[i] with p[N-1]
N--;
i--; // Continue processing with new p[i]
}
}
}
swap (p,0,min);
return p[0];
}
private void swap (Point p[], int a, int b)
{
Point temp = p[a];
p[a] = p[b];
p[b] = temp;
}
private int equal_angles ( int N, Point p[] )
{
int M=N,
j = 1;
for ( int i=2; i<N; i++ )
{
Point temp = p[i];
if ( cross_prod( p0, sorted_p[j], temp ) == 0 )
{
if ( java.lang.Math.abs(temp.x - p0.x) > java.lang.Math.abs(sorted_p[j].x- p0.x)
|| temp.y > sorted_p[j].y )
{
sorted_p[j] = temp;
M--;
}
else
M--;
}
else
{
j++;
sorted_p[j] = temp;
}
}
return M;
}
private void mergesort ( Point p[], int lo, int hi )
{
if (lo == hi)
return;
int mid = (lo + hi)/2;
mergesort( p, lo, mid );
mergesort( p, mid+1, hi);
merge( p, lo, mid, hi );
}
private void merge ( Point p[], int lo, int mid, int hi )
{
int cp=0,
k=0,
i=lo,
j=mid+1;
Point B[];
B = new Point[hi-lo+1];
while ( (i<= mid) && (j<=hi) )
{
cp = cross_prod( p0, p[i], p[j] );
if ( cp <= 0 )
B[k++] = p[i++];
else
B[k++] = p[j++];
}
while ( i<=mid )
B[k++] = p[i++];
while ( j<=hi )
B[k++] = p[j++];
for (k=0; k<(hi-lo+1); k++)
p[lo+k] = B[k];
}
private int cross_prod( Point a, Point b, Point c )
{
return ( (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y) );
}
public void geometryStart(Point a[])
{
scan (a);
}
}