package algs91; // section 9.8
import stdlib.*;
import java.util.Arrays;
import algs12.Point2D;
import algs13.Stack;
/* ***********************************************************************
 *  Compilation:  javac GrahamScan.java
 *  Execution:    java GrahamScan < input.txt
 *  Dependencies: Point2D.java
 *
 *  Create points from standard input and compute the convex hull using
 *  Graham scan algorithm.
 *
 *  May be floating-point issues if x- and y-coordinates are not integers.
 *
 *  % java GrahamScan < rs1423.txt
 *  (24690.0, 216.0)
 *  (32420.0, 756.0)
 *  (32706.0, 20013.0)
 *  (32373.0, 20274.0)
 *  (31776.0, 20523.0)
 *  (13443.0, 28086.0)
 *  (9252.0, 27747.0)
 *  (8286.0, 27555.0)
 *  (798.0, 22215.0)
 *  (954.0, 11163.0)
 *  (1833.0, 6300.0)
 *  (3804.0, 1017.0)
 *  (11196.0, 504.0)
 *
 *************************************************************************/

public class GrahamScan {
	private final Stack<Point2D> hull = new Stack<>();

	public GrahamScan(Point2D[] pts) {

		// defensive copy
		int N = pts.length;
		Point2D[] points = new Point2D[N];
		for (int i = 0; i < N; i++)
			points[i] = pts[i];

		// preprocess so that points[0] has lowest y-coordinate; break ties by x-coordinate
		// points[0] is an extreme point of the convex hull
		// (alternatively, could do easily in linear time)
		Arrays.sort(points);

		// sort by polar angle with respect to base point points[0],
		// breaking ties by distance to points[0]
		Arrays.sort(points, 1, N, points[0].POLAR_ORDER);

		hull.push(points[0]);       // p[0] is first extreme point

		// find index k1 of first point not equal to points[0]
		int k1;
		for (k1 = 1; k1 < N; k1++)
			if (!points[0].equals(points[k1])) break;
		if (k1 == N) return;        // all points equal

		// find index k2 of first point not collinear with points[0] and points[k1]
		int k2;
		for (k2 = k1 + 1; k2 < N; k2++)
			if (Point2D.ccw(points[0], points[k1], points[k2]) != 0) break;
		hull.push(points[k2-1]);    // points[k2-1] is second extreme point

		// Graham scan; note that points[N-1] is extreme point different from points[0]
		for (int i = k2; i < N; i++) {
			Point2D top = hull.pop();
			while (Point2D.ccw(hull.peek(), top, points[i]) <= 0) {
				top = hull.pop();
			}
			hull.push(top);
			hull.push(points[i]);
		}

		assert isConvex();
	}

	// return extreme points on convex hull in counterclockwise order as an Iterable
	public Iterable<Point2D> hull() {
		Stack<Point2D> s = new Stack<>();
		for (Point2D p : hull) s.push(p);
		return s;
	}

	// check that boundary of hull is strictly convex
	private boolean isConvex() {
		int N = hull.size();
		if (N <= 2) return true;

		Point2D[] points = new Point2D[N];
		int n = 0;
		for (Point2D p : hull()) {
			points[n++] = p;
		}

		for (int i = 0; i < N; i++) {
			if (Point2D.ccw(points[i], points[(i+1) % N], points[(i+2) % N]) <= 0) {
				return false;
			}
		}
		return true;
	}

	// test client
	public static void main(String[] args) {
		StdIn.fromFile ("data/rs1423.txt");

		int N = StdIn.readInt();
		Point2D[] points = new Point2D[N];
		for (int i = 0; i < N; i++) {
			int x = StdIn.readInt();
			int y = StdIn.readInt();
			points[i] = new Point2D(x, y);
		}
		GrahamScan graham = new GrahamScan(points);
		for (Point2D p : graham.hull())
			StdOut.println(p);
	}

}