Где у меня может быть ошибка в нахождении площади сложной фигуры?

Question

[Proshka17]

Условие задачи (осторожно, большие изображения)

Я написал решение, но получаю WA. Подскажите пожалуйста в чем я мог допустить ошибку?

Код моего решения

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <cmath>

using namespace std;


class Sol {
public:

  vector<double> leftborders;
  vector<vector<double>> leftvalues;

  vector<double> rightborders;
  vector<vector<double>> rightvalues;

  double sum = 0;


  double calc(double a, double b, double c, double left, double right) {
    double r1 = a * pow(right, 3) / 3;
    double r2 = b * pow(right, 2) / 2;
    double r3 = c * right;


    double l1 = a * pow(left, 3) / 3;
    double l2 = b * pow(left, 2) / 2;
    double l3 = c * left;


    return r1 + r2 + r3 - (l1 + l2 + l3);

  }

  void doit() {

    double liters = 1;
    double riters = 1;

    while (liters <= leftvalues.size()) {

      double rside = min(leftborders[liters], rightborders[riters]);
      double lside = max(leftborders[liters-1], rightborders[riters-1]);

      double comp_a = leftvalues[liters-1][0] - rightvalues[riters-1][0];
      double comp_b = leftvalues[liters-1][1] - rightvalues[riters-1][1];
      double comp_c = leftvalues[liters-1][2] - rightvalues[riters-1][2];

      double desc = comp_b * comp_b - 4 * comp_a * comp_c;

      vector<double> stones;  

      if (desc == 0) {
        if (comp_a != 0) {
          double p1 = (-1 * comp_b) / (2 * comp_a);
          if (p1 > lside&& p1 < rside) stones.push_back(p1);
        }
      }
      else if (desc > 0) {
        if (comp_a == 0) {
          double p0 = (-1 * comp_c) / comp_b;
          if (p0 > lside&& p0 < rside) stones.push_back(p0);
        }
        else {
          double p1 = (-1 * comp_b - sqrt(desc)) / (2 * comp_a);
          if (p1 > lside&& p1 < rside) stones.push_back(p1);

          double p2 = (-1 * comp_b + sqrt(desc)) / (2 * comp_a);
          if (p2 > lside&& p2 < rside) stones.push_back(p2);
        }
      }
      stones.push_back(rside);

      for (int i = 0; i < stones.size(); ++i) {
        double one = calc(leftvalues[liters-1][0], leftvalues[liters-1][1], leftvalues[liters-1][2],lside,stones[i]);
        double two = calc(rightvalues[riters-1][0], rightvalues[riters-1][1], rightvalues[riters-1][2],lside,stones[i]);
        sum += abs(one-two);
        lside = stones[i];
      }

      if (leftborders[liters] <= rightborders[riters]) {
        liters++;
      }
      else {
        riters++;
      }
      

    }

  }

};


int main() {

  ifstream f("input.txt");
  Sol s;
  double leftorder;
  double rightorder;
  f >> leftorder;
  f >> rightorder;
  for (double i = 0; i <= leftorder; ++i) {
    double tmp;
    f >> tmp;
    s.leftborders.push_back(tmp);
  }

  for (double i = 0; i < leftorder; ++i) {
    double tmp1;
    double tmp2;
    double tmp3;
    f >> tmp1;
    f >> tmp2;
    f >> tmp3;
    vector<double> vals;
    vals.push_back(tmp1);
    vals.push_back(tmp2);
    vals.push_back(tmp3);
    s.leftvalues.push_back(vals);
  }

  for (double i = 0; i <= rightorder; ++i) {
    double tmp;
    f >> tmp;
    s.rightborders.push_back(tmp);
  }

  for (double i = 0; i < rightorder; ++i) {
    double tmp1;
    double tmp2;
    double tmp3;
    f >> tmp1;
    f >> tmp2;
    f >> tmp3;
    vector<double> vals;
    vals.push_back(tmp1);
    vals.push_back(tmp2);
    vals.push_back(tmp3);
    s.rightvalues.push_back(vals);
  }


  s.doit();
  cout << fixed << setprecision(10) << s.sum;

  return 0;
}

Comments

[Mercury13]

Код ужоснах. Вы вообще пытались его запускать на настоящей кусочно-квадратичной функции, а не на той фигне, что приведена в примерах?

[Mercury13]

Подозрение, что код глючит на каких-то особых случаях.

[Mercury13]

Кроме того, вы странно считаете интеграл: у вас есть коэффициенты функции-разности — а вы считаете интегралы по отдельности.

[Proshka17]

Да, проверял на таком примере:

Разными цветами закрашены участки, которые считаются на разных итерациях цикла while
Подсчитал руками, ответ сошелся.
Интегралы считаются по отдельности, потому что могут быть точки пересечения функций. Поэтому интегралы считаются на участках получившихся из-за разбиения точками пересечения. Например в первой итерации приведенного примера есть точка пересечения, поэтому сначала считается интеграл от левой границы до точки пересечения, а потом от точки пересечения, до правой границы.

[Proshka17]

Mercury13, ошибка вываливается уже на 3 тесте, так уж думаю что есть более менее фундаментальная ошибка

[Mercury13]

Proshka17, Нет нужды — мы и без того находим эти точки пересечения и считаем до них.

[Mercury13]

Кроме того, я ОЧЕНЬ не советую использовать vector и pair вместо struct { a, b, c }. Ну, кроме случаев, когда есть реальная автоматизация.

[Mercury13]

Совпадение точек разбиения проверял? Совпадение кривых (a1=a2, b1=b2, c1=c2) проверял?

[Proshka17]

Mercury13, Совпадение кривых проверял, вроде работает, да и должно работать.
А точки разбиения добавляются только если не совпадают с границами.

[Модератор]

Proshka17, дорогой пользователь, настоятельно рекомендуем еще раз обратить самое пристальное внимание на п. 3.1 регламента работы сервиса (и, в особенности, на его последний абзац). В противном случае, ваши вопросы будут удаляться по причине тег-спама, а систематические нарушения приведут к блокировке учетной записи.

[Proshka17]

Модератор, Окей, не специально, "программирование" на первый взгляд относится к теме

[Mercury13]

Дальше. Два корня и comp_a < 0 работать не будут — корни не упорядочены.

[Proshka17]

Mercury13, Да, проблема была в этом.
Добавил сортировку точек и все сработало!
Спасибо!

[Mercury13]

Proshka17, Отметьте меня решением.

[Proshka17]

Mercury13, Отметил. Мне нужно решить еще одну задачу, но я никак не могу выбраться из n^2 сложности. Если посмотрите, буду очень благодарен!

Answer 1

[Mercury13]

Обсуждение было в комментах, и ключевая причина — при comp_a < 0 корни не сортируются.

Побочные проблемы кода.
1. Можно было интеграл разности, а не разность интегралов.
2. Лучше не использовать vector и pair на месте struct { a, b, c } — кроме случаев, когда есть важная автоматизация.

Answer 2

[Wataru]

Не совсем понятен ваш код слияния двух массивов отрезков. Я бы все промежуточные точки тупо загнал в один вектор и отсортировал. Ну или сделал стандартное слияние двух отсортированных массивов. Дальше в цикле считал бы на отрезке между двумя соседними точками (если длина отрезка хотя бы 1e-6), Параметры кривых ищутся легко - держите 2 счетчика, как у вас уже есть, и двигайте их, пока текущий отрезок для той или иной функции не станет закрываться позже начала текущего отрезка. Может ваш код и эквивалентен этому, но я в этом не уверен.

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

Еще, очевидная проблема вот: comp_a != 0. Флоаты нельзя никогда сравнивать точно. Только с епсилон:

x < y  ====> x < y - eps
x <= y ====> x < y + eps 
x == y ====> fabs(x-y) < eps
x != y ====> fabs(x-y) > eps

Comments

[Proshka17]

Добрый день!
Все получилось, нужно было добавить сортировку точек пересечения.
Мне осталось решить задачу про карты Как понять условие задачи?, если вы с ней поможете буду очень благодарен!

[Wataru]

Proshka17, я там ответил на ваш комментарий.

[Mercury13]

x < y ====> x < y - eps
x <= y ====> x < y + eps

Крайне редко, когда наличие или отсутствие точки в диапазоне что-то кардинально меняет.

[Mercury13]

x == y ====> fabs(x-y) < eps
x != y ====> fabs(x-y) > eps

Обычно да, но знаком со случаями, когда, например, цифры берутся из одного источника.

[Wataru]

Mercury13, для <= - да, но когда у вас проверка на неравнство нулю какого-то выражения - может на больших числах и получиться 0.00000000000003. Когда как численно - ответ 0.

[Mercury13]

wataru,

Когда как численно - ответ 0.

Имели в виду «аналитически»?

[Wataru]

Mercury13, Да.