数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究实现平面礼品包装算法的 C++ 程序
我们开发一个 C++ 程序，在两个维度上实现礼品包装算法。礼品包装算法是用于计算给定点集凸包的算法。
算法
Begin function convexHull() to find convex hull of a set of n points: There must be at least three points. Initialize the result. Find the leftmost point. Starting from leftmost point, keep moving counterclockwise until reach the start point again. Print the result. End
示例代码
#include <iostream>
using namespace std;
#define INF 10000
struct P {
int x;
int y;
};
int orient(P a, P b, P c) {
int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if (v == 0)
return 0; // colinear
return (v >0) ? 1 : 2; // clock or counterclock wise
}
void convexHull(P points[], int m) {
if (m < 3)//at least three points required
return;
int n[m];
for (int i = 0; i < m; i++)
n[i] = -1;
int l = 0;//initialize result.
for (int i = 1; i < m; i++)
if (points[i].x < points[l].x)
l = i; //find left most point
int p = l, q;
do {
q = (p + 1) % m;
for (int i = 0; i < m; i++)
if (orient(points[p], points[i], points[q]) == 2)
q = i;
n[p] = q;
p = q;
} while (p != l);
for (int i = 0; i < m; i++) {
if (n[i] != -1)
cout << "(" << points[i].x << ", " << points[i].y << ")\n";
}
}
int main() {
P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}};
cout << "The points in the convex hull are: ";
int n = sizeof(points) / sizeof(points[0]);
convexHull(points, n);
return 0;
}输出
The points in the convex hull are: (0, 4) (4, 1) (3, 0) (1, 1) (7, 6)
更新日期：2019 年 7 月 30 日
433 次浏览
广告