可以不用vector,<algorithm>头文件吗、
时间: 2023-08-16 19:09:39 浏览: 39
可以的,下面是不使用 vector 和 algorithm 头文件的实现:
```c++
#include <iostream>
using namespace std;
struct Point {
int x;
int y;
};
// 按照 x 坐标排序
void sortPoints(Point arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i].x > arr[j].x) {
swap(arr[i], arr[j]);
}
}
}
}
// 叉积计算
int crossProduct(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
// 求解凸包
int convexHull(Point arr[], int n, Point hull[]) {
int k = 0;
// 求下凸壳
for (int i = 0; i < n; i++) {
while (k >= 2 && crossProduct(hull[k - 2], hull[k - 1], arr[i]) <= 0) {
k--;
}
hull[k++] = arr[i];
}
// 求上凸壳
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && crossProduct(hull[k - 2], hull[k - 1], arr[i]) <= 0) {
k--;
}
hull[k++] = arr[i];
}
return k - 1;
}
// 合并凸包
int mergeConvexHull(Point left[], int nLeft, Point right[], int nRight, Point hull[]) {
int leftmost = 0, rightmost = 0;
for (int i = 1; i < nLeft; i++) {
if (left[i].x < left[leftmost].x) {
leftmost = i;
}
}
for (int i = 1; i < nRight; i++) {
if (right[i].x > right[rightmost].x) {
rightmost = i;
}
}
int k = 0;
hull[k++] = left[leftmost];
hull[k++] = right[rightmost];
int l = leftmost, r = rightmost;
while (l < nLeft - 1 || r > 0) {
if (l == nLeft - 1) {
hull[k++] = right[--r];
} else if (r == 0) {
hull[k++] = left[++l];
} else {
int cp = crossProduct(left[l], right[r], right[r - 1]);
if (cp > 0) {
hull[k++] = right[--r];
} else {
hull[k++] = left[++l];
}
}
}
return k;
}
// 分治求解凸包
int divideAndConquerConvexHull(Point arr[], int n, Point hull[]) {
if (n <= 1) {
hull[0] = arr[0];
return 1;
}
int mid = n / 2;
Point left[mid];
Point right[n - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < n; i++) {
right[i - mid] = arr[i];
}
Point hullLeft[mid + 1];
Point hullRight[n - mid + 1];
int nLeft = convexHull(left, mid, hullLeft);
int nRight = convexHull(right, n - mid, hullRight);
return mergeConvexHull(hullLeft, nLeft, hullRight, nRight, hull);
}
int main() {
Point arr[] = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {2, 4}, {3, 5}, {4, 3}, {5, 2}, {4, 0}, {3, 1}};
int n = sizeof(arr) / sizeof(arr[0]);
sortPoints(arr, n);
Point hull[n + 1];
int k = divideAndConquerConvexHull(arr, n, hull);
for (int i = 0; i < k; i++) {
cout << "(" << hull[i].x << ", " << hull[i].y << ")" << endl;
}
return 0;
}
```
以上代码实现了不使用 vector 和 algorithm 头文件的分治法求解凸包问题,其中 `sortPoints` 函数用于按照 x 坐标排序,`convexHull` 函数用于求解单组点集的凸包,`mergeConvexHull` 函数用于合并左右两组点集的凸包,`divideAndConquerConvexHull` 函数用于利用分治法求解凸包问题。