[已解决]凸包算法(convex hull)

kkken

我想问如要找很多组的凸包该如何实现, 用C++。谢谢。
例子：
输入
2（要找多少个）
5（第一个有5个坐标）
1 1
1 -1
0  0
-1 -1
-1 1
8（第二个有8个坐标）
1  0
0  1
0  -1
-1  0
2  0
0  2
0  -2
-2  0
输出
4（第一凸包由4个组成）
-1 -1
1 -1
1 1
-1 1
4（第二个凸包由4个组成）
-2  0
0  -2
0  2
2  0

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2021-11-12 22:08:10

题解：

#include <bits/stdc++.h>

struct Point{int x, y;};

int orientation(Point p, Point q, Point r)
{
        int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
        if (val == 0) return 0;
        return (val > 0)? 1: 2;
}


void convexHull(Point points[], int n)
{
        if (n < 3) return;
        std::vector<Point> hull;
        int l = 0;
        for (size_t i = 1; i < n; i++) if (points[i].x < points[l].x) l = i;
        int p = l, q;
        do
        {
            hull.push_back(points[p]);
                q = (p+1)%n;
                for (size_t i = 0; i < n; i++) if (orientation(points[p], points[i], points[q]) == 2) q = i;
                p = q;

        } while (p != l);
        std::cout << "\nConvex Hull: " << hull.size() << "points" << std::endl;
        for (size_t i = 0; i < hull.size(); i++) std::cout << hull[i].x << ' ' << hull[i].y << std::endl;
        std::cout << std::endl;
}


int main()
{
        int N, T;
        std::cin >> T;
        for(size_t t = 0; t < T; t++){
            std::cin >> N;
            Point points[N];
            for(size_t i = 0; i < N; i++){
                int x, y;
                std::cin >> x >> y;
                points[i].x = x;
                points[i].y = y;
            }
            int n = sizeof(points)/sizeof(points[0]);
            convexHull(points, n);
        }
        
        return 0;
}

输入/输出：

2
5
1 1
1 -1
0  0
-1 -1
-1 1

Convex Hull: 4points
-1 -1
1 -1
1 1
-1 1

8
1  0
0  1
0  -1
-1  0
2  0
0  2
0  -2
-2  0

Convex Hull: 4points
-2 0
0 -2
2 0
0 2

我知道可以用 using namespace std，但是我比较喜欢不用命名空间

跳转到最佳答案楼层

傻眼貓咪

题解：

#include <bits/stdc++.h>

struct Point{int x, y;};

int orientation(Point p, Point q, Point r)
{
        int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
        if (val == 0) return 0;
        return (val > 0)? 1: 2;
}


void convexHull(Point points[], int n)
{
        if (n < 3) return;
        std::vector<Point> hull;
        int l = 0;
        for (size_t i = 1; i < n; i++) if (points[i].x < points[l].x) l = i;
        int p = l, q;
        do
        {
            hull.push_back(points[p]);
                q = (p+1)%n;
                for (size_t i = 0; i < n; i++) if (orientation(points[p], points[i], points[q]) == 2) q = i;
                p = q;

        } while (p != l);
        std::cout << "\nConvex Hull: " << hull.size() << "points" << std::endl;
        for (size_t i = 0; i < hull.size(); i++) std::cout << hull[i].x << ' ' << hull[i].y << std::endl;
        std::cout << std::endl;
}


int main()
{
        int N, T;
        std::cin >> T;
        for(size_t t = 0; t < T; t++){
            std::cin >> N;
            Point points[N];
            for(size_t i = 0; i < N; i++){
                int x, y;
                std::cin >> x >> y;
                points[i].x = x;
                points[i].y = y;
            }
            int n = sizeof(points)/sizeof(points[0]);
            convexHull(points, n);
        }
        
        return 0;
}

输入/输出：

2
5
1 1
1 -1
0  0
-1 -1
-1 1

Convex Hull: 4points
-1 -1
1 -1
1 1
-1 1

8
1  0
0  1
0  -1
-1  0
2  0
0  2
0  -2
-2  0

Convex Hull: 4points
-2 0
0 -2
2 0
0 2

我知道可以用 using namespace std，但是我比较喜欢不用命名空间

傻眼貓咪

兄弟，如果解答对你有帮助，请给最佳解答，谢谢