我解决了以下问题。
有两个函数f（x）和g（x）。它们每个都分为几部分。 f（x）函数由'n'部分组成，而g（x）由'm'部分组成。每个部分都表示为第二级多项式函数（ax ^ 2 + bx + c）。我们需要在f（x）和g（x）之间找到一个精度为10 ^（-6）的区域。
输入数据：
n，m（1 <= n，m <= 10 ^ 5）;
f（x）的边界点； // n + 1分
f（x）的多项式； // n个字符串（a，b，c表示ax ^ 2 + bx + c）
g（x）的边界点； // m + 1分
g（x）的多项式； // m个字符串（a，b，c表示ax ^ 2 + bx + c）
功能的第一和最后一点是相等的。
样本输入：
1 1
0 1
1 -2 1
0 1
-1 2 1
输出：
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;
}
该程序未通过某些测试。答案错误。
可能是什么问题？
为了找到两条曲线之间的区域，您必须执行以下操作：
如果功能不是兼而有之，则需要稍加调整。幸运的是，您所有的函数都是多项式，因此可以以显式形式编写反导数。
曲线下的面积（曲线和零横坐标之间的面积）和两条垂直线是范围上函数的积分（确定积分）。
首先，您必须确定所有唯一范围，其中只有g(x)组中的一个功能与f(x)组中的一个功能配对。通常情况下，该数字可以大于n和m。
在每个找到的范围内，区域是功能abs(f(x)-g(x))的整数
由于提供了函数，因此可以通过找到all方程的解来找到（f）与g（x）之间的交点。
(af - ag) * x^2 + (bf - bg) * x + cf - cg = 0
如果行列式为负，则它们不相交。如果解决方案超出特定范围，则这些特定片段不会相交。
解决方案用于进一步划分范围。因此，理论上范围可以保持不变，也可以用三个范围代替。为了方便地修改列表或范围，可能是谨慎的做法。
h(x) = f(x) - g(x)的计算absolute积分值。您具有分析形式的功能，因此可以进行分析。
如果H(x)是h(x)的反导数，并且h（x）是单调的（我们确保查找交点之间的范围），则在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的很小或很大的值都可能降低精度）。无论如何，有很多离散算法来评估其定积分和精度。
在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都是可变长度数组（某些编译器提供的非标准扩展名），而应该全部是标准容器，例如[ C0]。
发布的代码还使用std::vector存储所有点并确保其顺序。如果边界点已经在它们自己的范围内排序，则这可能不是实现该结果的最有效方法。
[std::set，测试了可能的不同实现。