package package01;

 import java.util.Arrays;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.Point2D;

 import edu.princeton.cs.algs4.Stack;

 public class class01

 {

     private Stack<Point2D> hull = new Stack<Point2D>();

     public class01(Point2D[] points)

     {

         if (points == null || points.length == 0)

             throw new IllegalArgumentException("argument is null");

         int n = points.length;

         Point2D[] a = new Point2D[n];

         for (int i = 0; i < n; i++)

             a[i] = points[i];

         Arrays.sort(a);                             // Y 坐标升序排序，等值的按 X 坐标升序排序，保证 a[0] 为最下最左，a[1] 为

         Arrays.sort(a, 1, n, a[0].polarOrder());    // 以 a[0] 为原点，幅角升序排序

         hull.push(a[0]);                            // 第一个点

         int k1;                                     // 找到下一个相异点

         for (k1 = 1; k1 < n; k1++)

         {

             if (!a[0].equals(a[k1]))

                 break;

         }

         if (k1 == n)

             return;

         int k2;                                     // 找到下一个非共线点

         for (k2 = k1 + 1; k2 < n; k2++)

         {

             if (Point2D.ccw(a[0], a[k1], a[k2]) != 0)

                 break;

         }

         hull.push(a[k2 - 1]);                       // a[k2-1] 是与 a[0]，a[k1] 共线的最后一个点（也可以先压 a[k1] 然后跳过 a[k2-1]）

         for (int i = k2; i < n; i++)

         {

             Point2D top = hull.pop();

             for (; Point2D.ccw(hull.peek(), top, a[i]) <= 0; top = hull.pop()); // 倒数第 2 点、倒数第 1 点和当前点计算三角形面积，逆时针方向为正

                                                                                 // 吐栈吐到这 3 点的面积为正为止，压入倒数第 2 点当前点

             hull.push(top);

             hull.push(a[i]);

         }

         assert isConvex();

     }

     public Iterable<Point2D> hull()                 // 得到凸包的迭代器

     {

         Stack<Point2D> s = new Stack<Point2D>();

         for (Point2D p : hull)

             s.push(p);

         return s;

     }

     private boolean isConvex()                      // 检查凸性

     {

         int n = hull.size();

         if (n <= 2) return true;

         Point2D[] points = new Point2D[n];

         int k = 0;

         for (Point2D p : hull())

             points[k++] = 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;

     }

     public static void main(String[] args)

     {

         int n = StdIn.readInt();

         Point2D[] points = new Point2D[n];

         for (int i = 0; i < n; i++)

         {

             int x = StdIn.readInt(), y = StdIn.readInt();

             points[i] = new Point2D(x, y);

         }

         class01 graham = new class01(points);

         for (Point2D p : graham.hull())

             StdOut.println(p);

     }

 }

 package package01;

 import edu.princeton.cs.algs4.StdIn;

 import edu.princeton.cs.algs4.StdOut;

 import edu.princeton.cs.algs4.Point2D;

 import edu.princeton.cs.algs4.GrahamScan;

 public class class01

 {

     private Point2D best1, best2;

     private double bestDistanceSquared = Double.NEGATIVE_INFINITY;  // 当前最远点对距离的平方

     public class01(Point2D[] points)

     {

         if (points == null || points.length <= 1)

             throw new IllegalArgumentException("constructor argument is null");

         GrahamScan graham = new GrahamScan(points);

         int m = 0;// 凸包点数

         for (Point2D p : graham.hull())

             m++;

         Point2D[] hull = new Point2D[m + 1];                        // 凸包顶点放入 a[1] ~ a[m]

         m = 1;

         for (Point2D p : graham.hull())

             hull[m++] = p;

         m--;                                                        // m 等于凸包顶点数

         if (m == 1) // 所有点都相同

             return;

         if (m == 2) // 所有点共线

         {

             best1 = hull[1];

             best2 = hull[2];

             bestDistanceSquared = best1.distanceSquaredTo(best2);

             return;

         }

         int k = 2;

         for (; Point2D.area2(hull[m], hull[1], hull[k + 1]) > Point2D.area2(hull[m], hull[1], hull[k]); k++);   // a[k] 是距离直线 a[1]a[m] 最远的点

         int j = k;

         for (int i = 1; i <= k && j <= m; i++)                      // j 搜索后半部分，i 搜索前半部分

         {

             update(hull[i], hull[j]);                               // i 挪动一位，检查 a[i] 和 a[j] 距离是否更大

             for (j++; (j <= m) && Point2D.area2(hull[i], hull[i + 1], hull[j]) > Point2D.area2(hull[i], hull[i + 1], hull[j - 1]); j++)

                                                                     // j 挪动保持 a[j] 远离直线 a[i]a[i+1]

                 update(hull[i], hull[j]);

         }

     }

     private void update(Point2D x, Point2D y)

     {

         double distanceSquared = x.distanceSquaredTo(y);

         if (distanceSquared > bestDistanceSquared)

         {

             best1 = x;

             best2 = y;

             bestDistanceSquared = distanceSquared;

         }

     }

     public Point2D either()

     {

         return best1;

     }

     public Point2D other()

     {

         return best2;

     }

     public double distance()

     {

         return Math.sqrt(bestDistanceSquared);

     }

     public static void main(String[] args)

     {

         int n = StdIn.readInt();

         Point2D[] points = new Point2D[n];

         for (int i = 0; i < n; i++)

         {

             int x = StdIn.readInt(), y = StdIn.readInt();

             points[i] = new Point2D(x, y);

         }

         class01 farthest = new class01(points);

         StdOut.println(farthest.distance() + " from " + farthest.either() + " to " + farthest.other());

     }

 }