用c++实现已知直角坐标系中的n个点，返回这些点的边界点连线的多边形

这个问题可以使用凸包算法来解决。凸包是一个用线段连接边界点的多边形，这个算法可以在几何学和计算几何中广泛应用。
以下是使用 C++ 实现的 Graham 扫描算法的伪代码，该算法可以在 O(nlogn) 的时间内解决问题：
struct Point {
int x, y;
};

bool cmp(Point a, Point b) {
if (a.x != b.x) {
return a.x < b.x;
} else {
return a.y < b.y;
}
}

bool ccw(Point a, Point b, Point c) {
return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x);
}

vector<Point> convex_hull(vector<Point>&amp; points) {
int n = points.size();
sort(points.begin(), points.end(), cmp);

vector<Point> hull;
for (int i = 0; i < n; i++) {
while (hull.size() >= 2 &amp;&amp; !ccw(hull[hull.size() - 2], hull[hull.size() - 1], points[i])) {
hull.pop_back();
}
hull.push_back(points[i]);
}

int t = hull.size() + 1;
for (int i = n - 2; i >= 0; i--) {
while (hull.size() >= t &amp;&amp; !ccw(hull[hull.size() - 2], hull[hull.size() - 1], points[i])) {
hull.pop_back();
}
hull.push_back(points[i]);
}

hull.pop_back();
return hull;
}
登录后复制
该算法首先按照 x 坐标进行排序，然后将点插入到凸包中。在每个新点插入后，检查是否需要删除凸包中的点以保持凸包的性质。这是通过检查新点是否在当前凸包的右侧来完成的。在最后，我们还需要删除重复的点。
使用该函数，您可以将点存储在一个 std::vector<Point> 中，并将返回的凸包存储在另一个 std::vector<Point> 中。