分治法计算三角形总面积 - C++ 代码实现

#include<bits/stdc++.h> using namespace std; inline static const nullptr_t _={ ios_base::sync_with_stdio(0); cin.tie(nullptr),cout.tie(nullptr); return nullptr; }(); double distance(int x1, int y1, int x2, int y2) { return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); } double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) { double area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)); return area; } double totalTriangleArea(vector<pair<int, int>>& points) { int n = points.size(); double totalArea = 0.0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { int x1 = points[i].first; int y1 = points[i].second; int x2 = points[j].first; int y2 = points[j].second; int x3 = points[k].first; int y3 = points[k].second; double area = triangleArea(x1, y1, x2, y2, x3, y3); totalArea += area; } } } return totalArea; } int main() { int n; cin>>n; vector<pair<int, int>> points(n); for(int i=0;i<n;i++) cin>>points[i].first>>points[i].second; double result=totalTriangleArea(points); cout<<fixed<<setprecision(1)<<result<<' '; return 0; }//如何使用分治法

分治法是一种将问题分解成较小子问题并逐个解决的方法。对于计算三角形的总面积，可以使用分治法来解决。

首先，将给定的点集按照x坐标进行排序，然后将点集分成两个子集。分别计算两个子集中的三角形总面积。

然后，将两个子集的总面积相加，得到整个点集的总面积。

具体步骤如下：

1. 将给定的点集按照x坐标进行排序。

2. 将点集分成两个子集，分别计算两个子集中的三角形总面积。可以使用递归来实现这一步骤。

   • 如果点集中的点个数小于等于3个，则直接计算三角形的面积并返回。

   • 否则，将点集分成两个子集，分别计算两个子集中的三角形总面积。

3. 将两个子集的总面积相加，得到整个点集的总面积。

4. 返回整个点集的总面积。

代码示例：

#include<bits/stdc++.h>
using namespace std;

double distance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) {
    double area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
    return area;
}

double totalTriangleArea(vector<pair<int, int>>& points, int start, int end) {
    int n = end - start + 1;
    if (n <= 3) {
        double totalArea = 0.0;
        for (int i = start; i <= end - 2; i++) {
            for (int j = i + 1; j <= end - 1; j++) {
                for (int k = j + 1; k <= end; k++) {
                    int x1 = points[i].first;
                    int y1 = points[i].second;
                    int x2 = points[j].first;
                    int y2 = points[j].second;
                    int x3 = points[k].first;
                    int y3 = points[k].second;
                    double area = triangleArea(x1, y1, x2, y2, x3, y3);
                    totalArea += area;
                }
            }
        }
        return totalArea;
    }
    else {
        int mid = (start + end) / 2;
        double area1 = totalTriangleArea(points, start, mid);
        double area2 = totalTriangleArea(points, mid + 1, end);
        return area1 + area2;
    }
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].first >> points[i].second;
    }
    sort(points.begin(), points.end());
    double result = totalTriangleArea(points, 0, n - 1);
    cout << fixed << setprecision(1) << result << '
';
    return 0;
}

注意：在分治法中，对于每个子集的计算，可以使用暴力法来计算三角形的面积。但是，由于输入规模较大，暴力法可能会超时。可以根据实际情况选择优化算法来计算三角形的面积。