C++增量法分治

### C++ 中增量法和分治法的实现与应用 #### 增量法 (Incremental Method) 增量法是一种逐步构建解决方案的方法，在许多领域都有广泛应用，尤其是在几何问题中。例如，引用中的三维凸包问题可以采用增量算法解决[^4]。 以下是基于引用内容的一个简单增量法实现： ```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; struct Point { double x, y, z; }; // 判断点 p 是否在平面 abc 同侧 bool same_side(const Point& a, const Point& b, const Point& c, const Point& p, const Point& q) { // 计算叉积 auto cross = [&](const Point& u, const Point& v) -> Point { return {v.y*u.z - v.z*u.y, v.z*u.x - v.x*u.z, v.x*u.y - v.y*u.x}; }; Point ab = {b.x - a.x, b.y - a.y, b.z - a.z}; Point ac = {c.x - a.x, c.y - a.y, c.z - a.z}; Point n = cross(ab, ac); double d1 = (p.x-a.x)*n.x + (p.y-a.y)*n.y + (p.z-a.z)*n.z; double d2 = (q.x-a.x)*n.x + (q.y-a.y)*n.y + (q.z-a.z)*n.z; return d1 * d2 >= 0; } void incremental_convex_hull(vector<Point>& points) { if (points.size() < 4) return; // 至少需要四个点 vector<vector<int>> hull; // 初始化三角形面片 hull.push_back({0, 1, 2}); hull.push_back({2, 1, 0}); for (size_t i = 3; i < points.size(); ++i) { vector<vector<int>> new_faces; for (auto& face : hull) { bool visible = false; // 如果当前点在面的一侧，则保留此面 if (!same_side(points[face[0]], points[face[1]], points[face[2]], points[i], points[0])) { new_faces.push_back(face); continue; } // 构造新的面 for (int j = 0; j < 3; ++j) { int k = (j + 1) % 3; vector<int> edge = {face[j], face[k], static_cast<int>(i)}; // 避免重复边 bool duplicate = false; for (auto& f : new_faces) { if ((f[0] == edge[0] && f[1] == edge[1]) || (f[0] == edge[1] && f[1] == edge[0])) { duplicate = true; break; } } if (!duplicate) new_faces.push_back(edge); } } hull = move(new_faces); } // 输出最终的凸壳 for (auto& face : hull) { cout << "(" << face[0] << ", " << face[1] << ", " << face[2] << ")" << endl; } } ``` --- #### 分治法 (Divide and Conquer) 分治法通过将大问题分解成多个子问题分别求解，最后合并结果得到整体解答。常见的应用场景包括排序（如快速排序）、查找（如二分查找），以及几何问题（如最近点对问题）。 以下是一个经典的分治法实现——寻找二维平面上的最近点对[^2]: ```cpp #include <bits/stdc++.h> using namespace std; struct Point { double x, y; }; double dist(const Point& a, const Point& b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } bool cmp_x(const Point& a, const Point& b) { return a.x < b.x; } bool cmp_y(const Point& a, const Point& b) { return a.y < b.y; } double closest_pair_divide_conquer(vector<Point>& points_sorted_by_x, vector<Point>& points_sorted_by_y, int l, int r) { if (r - l <= 3) { double min_dist = DBL_MAX; for (int i = l; i < r; ++i) { for (int j = i + 1; j < r; ++j) { min_dist = min(min_dist, dist(points_sorted_by_x[i], points_sorted_by_x[j])); } } return min_dist; } int mid = (l + r) / 2; double mid_line = points_sorted_by_x[mid].x; vector<Point> left_set(points_sorted_by_x.begin()+l, points_sorted_by_x.begin()+mid+1); vector<Point> right_set(points_sorted_by_x.begin()+mid+1, points_sorted_by_x.begin()+r); sort(left_set.begin(), left_set.end(), cmp_y); sort(right_set.begin(), right_set.end(), cmp_y); double delta_left = closest_pair_divide_conquer(points_sorted_by_x, left_set, l, mid+1); double delta_right = closest_pair_divide_conquer(points_sorted_by_x, right_set, mid+1, r); double delta = min(delta_left, delta_right); vector<Point> strip; for (int i = l; i < r; ++i) { if (abs(points_sorted_by_x[i].x - mid_line) < delta) { strip.push_back(points_sorted_by_x[i]); } } sort(strip.begin(), strip.end(), cmp_y); for (int i = 0; i < strip.size(); ++i) { for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < delta; ++j) { delta = min(delta, dist(strip[i], strip[j])); } } return delta; } double find_closest_pair(vector<Point>& points) { vector<Point> sorted_points = points; sort(sorted_points.begin(), sorted_points.end(), cmp_x); return closest_pair_divide_conquer(sorted_points, sorted_points, 0, sorted_points.size()); } ``` --- #### 总结 - **增量法**适用于动态更新场景下的问题，比如在线添加新数据并维护结构。 - **分治法**适合静态数据集上的优化问题，能够显著降低时间复杂度。 两者各有优劣，具体选择取决于实际需求。