用c语言写一个程序,要求使用安德鲁算法求出一个点集的凸包
时间: 2023-02-22 17:54:44 浏览: 94
下面是一个使用 C 语言实现安德鲁算法求出点集凸包的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_POINTS 100
#define MAX_HULL_POINTS MAX_POINTS
typedef struct point
{
int x, y;
} Point;
Point hull[MAX_HULL_POINTS];
// 计算两点之间的距离
double distance(Point A, Point B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
// 判断三点关系,以 p2 为基点,返回 p1 和 p3 相对于 p2 的位置关系
int orientation(Point p1, Point p2, Point p3)
{
int val = (p3.y - p2.y) * (p2.x - p1.x) - (p2.y - p1.y) * (p3.x - p2.x);
if (val == 0) return 0;
return (val > 0) ? 1 : 2;
}
// 寻找凸包上的点
void andrew(Point points[], int n)
{
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].y < points[l].y || (points[i].y == points[l].y && points[i].x < points[l].x))
l = i;
Point temp = points[0];
points[0] = points[l];
points[l] = temp;
Point p1, p2;
p1 = points[0];
for (int i = 1; i < n; i++)
{
p2 = points[i];
while (i < n - 1 && orientation(p1, p2, points[i + 1]) == 0)
p2 = points[++i];
hull[++l] = p2;
p1 = p2;
}
int m = 1;
for (int i = n - 2; i >= 0; i--)
{
p2 = points[i];
while (i > 0 && orientation(hull[m - 1], hull[m], p2) == 0)
m--;
hull[++m] = p2;
}
int count = m;
printf("凸包上的点有:\n");
for (int i = 0; i < count; i++)
printf("(%d
阅读全文