你能用c++编写凸包求解的代码吗
时间: 2023-02-28 11:43:46 浏览: 97
凸包算法的程序(C++)
4星 · 用户满意度95%
当然,我可以帮助您编写c语言求解凸包的代码。下面是一个简单的示例代码,它使用了计算几何中的Andrew算法:
```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_POINTS 100000
#define INFINITY 1e9
#define eps 1e-9
struct Point
{
double x, y;
};
int n;
Point p[MAX_POINTS];
Point stk[MAX_POINTS];
int top;
double cross(Point A, Point B)
{
return A.x * B.y - A.y * B.x;
}
int cmp(const void *a, const void *b)
{
Point *A = (Point *)a, *B = (Point *)b;
if (fabs(A->x - B->x) > eps)
return A->x < B->x ? -1 : 1;
if (fabs(A->y - B->y) > eps)
return A->y < B->y ? -1 : 1;
return 0;
}
void init()
{
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
qsort(p, n, sizeof(Point), cmp);
top = 0;
}
void solve()
{
int i;
for (i = 0; i < n; i++)
{
while (top >= 2 && cross(stk[top - 1] - stk[top - 2], p[i] - stk[top - 2]) <= eps)
top--;
stk[top++] = p[i];
}
int t = top + 1;
for (i = n - 2; i >= 0; i--)
{
while (top >= t && cross(stk[top - 1] - stk[top - 2], p[i] - stk[top - 2]) <= eps)
top--;
stk[top++] = p[i];
}
top--;
}
int main()
{
init();
solve();
int i;
for (i = 0; i < top; i++)
printf("%.0lf %.0lf\n", stk[i].x, stk[i].y);
return 0;
}
```
希望这个代码对您有所帮助!
阅读全文