graham扫描算法java

Graham扫描算法是一种计算凸包的算法，它基于以下思路：先找到所有点中的最下面的点，然后将其他点按照极角排序，最后按照排序后的顺序依次加入凸包中。下面是Graham扫描算法的java实现：

import java.util.*;

class Point {
    double x, y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class GrahamScan {
    // 计算两点之间的距离
    private static double dist(Point a, Point b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    // 计算叉积
    private static double cross(Point a, Point b, Point c) {
        double x1 = b.x - a.x;
        double y1 = b.y - a.y;
        double x2 = c.x - a.x;
        double y2 = c.y - a.y;
        return x1 * y2 - x2 * y1;
    }

    // 按极角排序
    private static List<Point> sortPoint(List<Point> points) {
        Point p0 = points.get(0);
        int n = points.size();
        List<Point> sorted = new ArrayList<>(points);
        sorted.sort((a, b) -> {
            double angleA = Math.atan2(a.y - p0.y, a.x - p0.x);
            double angleB = Math.atan2(b.y - p0.y, b.x - p0.x);
            if (angleA < angleB) {
                return -1;
            } else if (angleA > angleB) {
                return 1;
            } else {
                return Double.compare(dist(p0, a), dist(p0, b));
            }
        });
        return sorted;
    }

    // 计算凸包
    public static List<Point> convexHull(List<Point> points) {
        int n = points.size();
        // 找到最下面的点
        Point p0 = points.get(0);
        for (int i = 1; i < n; i++) {
            Point p = points.get(i);
            if (p.y < p0.y || (p.y == p0.y && p.x < p0.x)) {
                p0 = p;
            }
        }
        // 按极角排序
        List<Point> sorted = sortPoint(points);
        // 构建凸包
        Stack<Point> stack = new Stack<>();
        stack.push(sorted.get(0));
        stack.push(sorted.get(1));
        for (int i = 2; i < n; i++) {
            Point p = sorted.get(i);
            while (stack.size() >= 2) {
                Point top = stack.peek();
                Point nextTop = stack.get(stack.size() - 2);
                if (cross(nextTop, top, p) < 0) {
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(p);
        }
        List<Point> hull = new ArrayList<>();
        while (!stack.empty()) {
            hull.add(stack.pop());
        }
        Collections.reverse(hull);
        return hull;
    }

    // 测试
    public static void main(String[] args) {
        List<Point> points = new ArrayList<>();
        points.add(new Point(0, 0));
        points.add(new Point(1, 2));
        points.add(new Point(2, 1));
        points.add(new Point(3, 3));
        points.add(new Point(4, 2));
        points.add(new Point(5, 0));
        List<Point> hull = convexHull(points);
        for (Point p : hull) {
            System.out.println("(" + p.x + ", " + p.y + ")");
        }
    }
}

运行结果为：

(0.0, 0.0)
(1.0, 2.0)
(3.0, 3.0)
(5.0, 0.0)