graham scan算法

Graham Scan算法是一种计算凸包的算法，它的基本思想是将点集按照极角排序，然后依次将点加入凸包中。下面是Graham Scan算法的步骤：

1. 选取一个最低点作为起点，如果有多个最低点，选取最左边的那个点。

2. 将其余点按照极角和距离起点的距离排序。

3. 依次将排序后的点加入凸包中。加入一个点后，判断新的凸包是否还是凸包，如果不是凸包，则将凸包中不满足要求的点删除。

4. 最后得到的凸包即为所求。

Graham Scan算法的时间复杂度为O(nlogn)，其中n为点的个数。由于需要排序，所以算法的实现需要考虑排序算法的选择。

相关问题

凸包问题-graham-scan算法c++实现

好的，以下是Graham-Scan算法的C++实现代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;

struct point{
    double x,y;
};

point p[100005],s[100005];

inline double cross(point a,point b,point c){
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}

inline double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline bool cmp(point a,point b){
    double k=cross(a,b,p[1]);
    if(k>0||(k==0&&dis(a,p[1])<dis(b,p[1]))) return 1;
    else return 0;
}

int main(){
    int n,top=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>p[i].x>>p[i].y;
    for(int i=2;i<=n;++i)
        if(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x)) swap(p[i],p[1]);
    sort(p+2,p+n+1,cmp);
    s[++top]=p[1],s[++top]=p[2];
    for(int i=3;i<=n;++i){
        while(top>1&&cross(p[i],s[top],s[top-1])>=0) top--;
        s[++top]=p[i];
    }
    double ans=0;
    s[top+1]=s[1];
    for(int i=1;i<=top;++i) ans+=dis(s[i],s[i+1]);
    printf("%.2lf",ans);
    return 0;
}

其中，结构体`point`表示一个点，`cross()`函数计算两个向量的叉积，`dis()`函数计算两个点之间的距离。在`cmp()`函数中，比较两个点的大小，用于在排序时确定极角大小。在主函数中，先输入点的数量和坐标，然后找到y坐标最小的点p[1]，按极角排序，将凸包上的点存入栈s中，最后计算凸包周长。

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)