找出两个函数之间的区域

Question

我解决了下面的问题

There are two functions f(x) and g(x). Each of them is divided into parts. The f(x) function consists of 'n' parts, and g(x) consists of 'm' parts. Each part is represented as a Second-Degree Polynomial Function (ax^2 + bx + c). We need to find an area between f(x) and g(x) with precision 10^(-6).

Input data:

n, m (1 <= n, m <= 10^5);

boundary points of f(x); //n+1 points

polynomials of f(x); //n strings (a, b, c for ax^2 + bx + c)

boundary points of g(x); //m+1 points

polynomials of g(x); //m strings (a, b, c for ax^2 + bx + c)

The first and last points of the functions are equal.

示例输入：

输出:

1.3333333333

这是我的代码：

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


long double integrate(int f[3], int g[3], long double left, long double right) {
    long double a = f[0] - g[0], b = f[1] - g[1], c = f[2] - g[2];
    long double up = (a * right * right * right) / 3 + (b * right * right) / 2 + c * right;
    long double down = (a * left * left * left) / 3 + (b * left * left) / 2 + c * left;
    return (up > down) ? up - down : down - up;
}

void solve(int f[3], int g[3], int left, int right, long double &sum) {

    long double a = f[0] - g[0], b = f[1] - g[1], c = f[2] - g[2];
    if (a == 0) {
        if (b != 0) {
            long double x = -c/b;
            if (x > left && x < right) {
                sum += integrate(f, g, left, x);
                sum += integrate(f, g, x, right);
            }
        } else {
            sum += integrate(f, g, left, right);
        }
        return;
    }

    long double discriminant = b * b - 4 * a * c;
    if (discriminant < 0) { sum += integrate(f, g, left, right); }
    else {
        long double q = b >= 0 ? (-b - sqrt(discriminant))/2 : (-b + sqrt(discriminant))/2;
        long double x1 = q / a, x2 = c / q;
        if (discriminant == 0.0) {
            if (x1 > left && x1 < right) {
                sum += integrate(f, g, left, x1);
                sum += integrate(f, g, x1, right);
            } else {
                sum += integrate(f, g, left, right);
            }
        } else {
            long double first = min(x1, x2), second = max(x1, x2);
            if (first > left && first < right) {
                sum += integrate(f, g, left, first);
                if (second > left && second < right) {
                    sum += integrate(f, g, first, second);
                    sum += integrate(f, g, second, right);
                } else {
                    sum += integrate(f, g, first, right);
                }
            } else if (second > left && second < right) {
                sum += integrate(f, g, left, second);
                sum += integrate(f, g, second, right);
            } else {
                sum += integrate(f, g, left, right);
            }
        }
    }
    return;
}


int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;

    int f[n+1];
    int ffunc[n][3];
    int g[m+1];
    int gfunc[m][3];
    set <int> points;

    for (int i = 0; i < n+1; i++) {
        cin >> f[i];
        points.insert(f[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 3; k++) {
            cin >> ffunc[i][k];
        }
    }

    for (int i = 0; i < m+1; i++) {
        cin >> g[i];
        points.insert(g[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < 3; k++) {
            cin >> gfunc[i][k];
        }
    }

    int fit = 0, git = 0;
    long double sum = 0.0;
    auto it1 = points.begin();
    auto it2 = points.begin();
    it2++;
    while (it2 != points.end()) {

        solve(ffunc[fit], gfunc[git], *it1, *it2, sum);

        if (f[fit+1] == *it2) {
            fit++;
        }
        if (g[git+1] == *it2) {
            git++;
        }
        it1++;
        it2++;
    }
    cout.precision(27);
    cout << sum;
    return 0;
}

程序没有通过一些测试。它得到错误的答案。

可能是什么问题？

Answer 1

为了找到两条曲线之间的面积，您必须执行以下操作：

找到两条曲线相交的点，这些点将 x 轴分成几段。
对于每个段，计算两条曲线中每条曲线的积分，这给出了该段每条曲线下的面积。
在每一段中，一条曲线在另一条曲线上方，一条曲线在另一条曲线下方。从上面函数的面积中减去下面函数的面积。这给出了曲线之间的面积。
总结您为每个细分找到的结果。

这需要稍微调整一下，以防函数不都是非负的。幸运的是，你所有的函数都是多项式，所以可以写出显式的反导数。

Answer 2

曲线下面积（曲线与零横坐标之间的面积）和两条垂直线是函数在极差上的积分（定积分）。

首先，您必须确定所有唯一范围，其中只有 g(x) 集中的一个函数与 f(x) 集中的一个函数配对。在一般情况下，该数字可以大于 n 和 m.

在每个找到的范围区域是函数的积分abs(f(x)-g(x))
因为你有给定的函数，你可以通过找到方程的所有个解来找到(f)和g(x)之间的交点。

(af - ag) * x^2 + (bf - bg) * x + cf - cg = 0

如果行列式为负，则它们不相交。如果解决方案超出特定范围，则这些特定片段不会相交。
解决方案用于进一步划分范围。所以理论上范围可以保持不变或由三个范围代替。拥有一个列表或范围以便能够轻松修改它可能是明智的。
计算每个范围内函数h(x) = f(x) - g(x)的绝对积分值。你有分析形式的函数，所以你可以分析地做到这一点。

如果 H(x) 是 h(x) 的反导数并且 h(x) 是单调的（我们确保通过 finding ranges between intersections) ，那么第 i 个范围内的积分是 S[i] = H(x[i]) - H(x[i-1])，其中 x[i-1] 和 x[i] 是定义范围边界的 x 值。

计算的精度在那里是一个奇怪的部分，也许实际要求（被 OP 忽略了？）是以离散方式执行积分，同样，我们最好使用单调 h(x) 而不是 abs(f(x)-g(x)) 以排除由交叉点引起的不精确性。对于解析解，如果使用 float，我希望精度为 10^-9，尽管真正的绝对精度在很大程度上取决于值（非常小或大的 x 值可能会降低精度）。无论如何，有许多离散算法来评估它的定积分和精度。

Answer 3

在solve中，至少有一个特殊情况没有考虑到：

if (a == 0) {
    if (b != 0) {
        long double x = -c/b;
        if (x > left && x < right) {
            sum += integrate(f, g, left, x);
            sum += integrate(f, g, x, right);
        }  
        // else {
        //     sum += integrate(f, g, left, right);
        // }
    } else {
        sum += integrate(f, g, left, right);
    }
    return;
}

在main中，局部变量f、ffunc、g和gfunc都是变长数组（提供的非标准扩展一些编译器）并且应该都是标准容器，如 std::vector.

发布的代码还使用 std::set 来存储所有点并确保它们的顺序。如果边界点已经在它们自己的范围内排序，这可能不是实现该结果的最有效方法。

Here，测试了可能的不同实现。

找出两个函数之间的区域

Find the area between two functions

c++

area

curve

calculus