Найти область между двумя функциями

Question

Я решаю следующую проблему.

Есть две функции f (x) и g (x). Каждый из них делится на части. Функция f (x) состоит из «n» частей, а функция g (x) состоит из «m» частей. Каждая часть представлена ​​как полиномиальная функция второй степени (ax ^ 2 + bx + c). Нам нужно найти область между f (x) и g (x) с точностью 10 ^ (- 6).

Входные данные:

• n, м ( 1 <= n, m <= 10 ^ 5); </p>

• граничные точки f (x); // n + 1 балл

• многочлены от f (x); // n строк (a, b, c для топора ^ 2 + bx + c)

• граничные точки g (x); // m + 1 балл

• полиномов от g (x); // m строк (a, b, c для топора ^ 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;
}

Программа не проходит некоторые тесты. Он получает неправильный ответ.

В чем может быть проблема?

Answer 1

Площадь под кривой (площадь между кривой и нулевой абсциссой) и две вертикальные линии являются интегралом функции от диапазона (определенный интеграл).

1. Сначала необходимо определить все уникальные диапазоны где только одна функция из набора g(x) связана с функцией из набора f(x). В общем случае это число может быть больше, чем n и m.

   . В каждом найденном диапазоне диапазон является интегральной функцией abs(f(x)-g(x))

2. Поскольку у вас есть По заданным функциям вы можете найти точки пересечения между (f) и g (x), найдя все решения уравнения.

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

   Если определитель отрицательный они не пересекаются. Если решение выходит за пределы определенного диапазона, эти конкретные фрагменты не пересекаются.

3. Решения используются для дальнейшего разделения диапазонов. Теоретически диапазон может оставаться неизменным или заменяться тремя диапазонами. Вероятно, было бы целесообразно иметь список или диапазоны, чтобы можно было легко изменять его.

4. Рассчитать абсолютное значение интеграла для функции h(x) = f(x) - g(x) в каждом диапазоне. У вас есть функции в аналитической форме, так что вы можете сделать это аналитически.

   Если H(x) является антипроизводным h(x), а h (x) монотонно c (мы убедились, что путем нахождения диапазонов между пересечениями) , тогда интеграл в i -ом диапазоне равен S[i] = H(x[i]) - H(x[i-1]), где x[i-1] и x[i] являются значениями x, которые определяют границы диапазона.

   Точность вычислений является странной частью, возможно, фактическое требование (опущено OP?) Состоит в том, чтобы выполнять интеграцию дискретным способом, опять же, мы бы лучше использовали монотонное c h(x), чем abs(f(x)-g(x)) исключить неточность, вызванную пересечениями. С аналитическим решением я ожидаю, что точность будет 10 ^ -9, если используется float, хотя реальная абсолютная точность будет сильно зависеть от значений (очень маленькие или большие значения x могут снизить точность). В любом случае, существует множество дискретных алгоритмов для оценки определенного интеграла и точности его.

Answer 2

В 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 для хранения всех точек и обеспечить их порядок. Возможно, это не самый эффективный способ достижения sh такого результата, если граничные точки уже упорядочены в своих собственных диапазонах.

Здесь проверяется возможная другая реализация.

Answer 3

Чтобы найти область между двумя кривыми, вы должны сделать следующее:

1. Найти точки, в которых две кривые пересекаются, они разделяют ось x на сегменты.
2. Для каждого сегмента вычислите интеграл для каждой из двух кривых, это дает площадь под каждой кривой для этого сегмента.
3. В каждом сегменте у вас есть одна кривая, которая выше другой, и одна, которая является под этим. Вычтите область функции ниже из области функции выше. Это дает область между кривыми.
4. Суммируйте результаты, которые вы нашли для каждого сегмента.

Это необходимо немного адаптировать, если функции не являются неотрицательными. К счастью, все ваши функции являются полиномами, поэтому можно записать антипроизводную в явном виде.