import java.util.*;

public class Hull {

  // Maintain hull points internally:
  private  Pointd[] hull;
  private int hullSize;

  // Constructor that takes the point set
  public Hull (Pointd[] points) {
    Pointd[] vertices;
    int i, n;

    // record the number of points in the point set:
    n = points.length;

    // 0. Make a copy of the vertices because we'll need to sort:
    vertices = new Pointd[n];
    for (i=0; i<n; i++)
      vertices[i] = new Pointd();
    System.arraycopy (points, 0, vertices, 0, n);

    // 1. Find the leftmost, lowest point (it is on the hull):
    int low = findLowest(vertices);

    // 2.0 Put the low in the first position:
    swap (vertices, 0, low);

    // 2.1 Sort vertices based on their polar angles in counterclockwise
    //    order around the leftmost lowest point. 
    HullSortComparator comp = new HullSortComparator(vertices[0]);
    Arrays.sort(vertices, 1, vertices.length-1, comp);

    // 3. Remove collinear points:
    n = removeCollinearPoints(vertices);

    // 4. Compute the Hull based on Graham's Scan:
    hull = grahamScan(vertices, n);

  }

  public int getSize() {
    return hullSize;
  }

  public Pointd[] getHull () {
    return hull;
  }

  private Pointd[] grahamScan(Pointd[] points, int numOfPoints) {

    // 1. Create a stack and initialize with the first three points:
    HullStack hstack = new HullStack (numOfPoints);
    hstack.pushNew(points[0]);
    hstack.pushNew(points[1]);
    hstack.pushNew(points[2]);

    // 2. Start scanning points:
    for (int i=3; i<numOfPoints; i++) {

      // 2.1 isHull check whether the top two points in the stack and the point
      //     this is scanning form a right turn or not.
      //     if right turn, then pop the top element.
      while (!hstack.isHull(points[i]))
        hstack.popTop();

      // 2.2 Push the point that is just scaned into the stack.
      hstack.pushNew(points[i]);
    }

    // 3. Return all points still on the stack:
    hullSize = hstack.getSize();
    return hstack.hullArray();
  }

  // Remove collinear points based on polar angles.
  private int removeCollinearPoints(Pointd[] points) {
    int size = 1;

    // Create a comparator for comparison based on polar angles.
    HullSortComparator comp = new HullSortComparator(points[0]);

    for (int i=2; i<points.length; i++) {
      if (comp.compare(points[size], points[i])==0) {
        if (points[size].y-points[0].y < points[i].y-points[0].y) {
          points[size] = points[i];
        }
      } else {
        size++;
        points[size]=points[i];
      }
    }
   
    return (size+1);
  }

  // Compute the lowest point (the point with smallest y-coordinate). Choose
  // the leftmost one in case of a tie.
  private int findLowest (Pointd[] points) {

    int n = points.length;

    if (n==0) return -1;

    double smallestY = points[0].y;
    int smallestIndex = 0;

    for (int i=1; i<n; i++) {
      if (points[i].y<smallestY) {
        smallestY = points[i].y;
        smallestIndex = i;
      } else if (points[i].y == smallestY) {
        if (points[i].x < points[smallestIndex].x) {
          smallestIndex = i;
        }
      }
    }

    return smallestIndex;
  }

  // Swap two points.
  private void swap (Pointd[] points, int i, int j) {
    Pointd temp = points[i];
    points[i] = points[j];
    points[j] = temp;
  }

}