資料結構
網路
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 次瀏覽
廣告