Advertisement
Guest User

Untitled

a guest
Feb 25th, 2020
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.09 KB | None | 0 0
  1. //#include "bits/stdc++.h"
  2. #include <iostream>
  3. #include <vector>
  4. #include <iomanip>
  5. #include <limits>
  6. #include <cmath>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll, ll> pll;
  14. typedef pair<ld, ld> pld;
  15. typedef pair<int, int> pii;
  16.  
  17. #define FOR(i, n) for (int i = 0; i < n; i++)
  18. #define PI acos(-1)
  19.  
  20. struct fun
  21. {
  22.     struct section
  23.     {
  24.         //y = ax2 + bx + c
  25.         int open, close, a, b, c;
  26.     };
  27.     vector<section> sections;
  28. } f, g;
  29.  
  30. void fill_f(int n)
  31. {
  32.     f.sections.resize(static_cast<size_t>(n));
  33.     FOR(i, n + 1)
  34.     {
  35.         int li;
  36.         cin >> li;
  37.         f.sections[i].open = li;
  38.         if (i - 1 >= 0) f.sections[i - 1].close = li;
  39.     }
  40.     FOR(i, n)
  41.     {
  42.         int a, b, c;
  43.         cin >> a >> b >> c;
  44.         f.sections[i].a = a;
  45.         f.sections[i].b = b;
  46.         f.sections[i].c = c;
  47.     }
  48. }
  49.  
  50. void fill_g(int m)
  51. {
  52.     g.sections.resize(static_cast<size_t>(m));
  53.     FOR(i, m + 1)
  54.     {
  55.         int ri;
  56.         cin >> ri;
  57.         g.sections[i].open = ri;
  58.         if (i - 1 >= 0) g.sections[i - 1].close = ri;
  59.     }
  60.     FOR(i, m)
  61.     {
  62.         int a, b, c;
  63.         cin >> a >> b >> c;
  64.         g.sections[i].a = a;
  65.         g.sections[i].b = b;
  66.         g.sections[i].c = c;
  67.     }
  68.  
  69. }
  70.  
  71. /**
  72.   1 1
  73.   0 1
  74.   0 0 1
  75.   0 1
  76.   0 0 2
  77.  
  78.   ans = 1.0000000000
  79.  
  80.   1 1
  81.   0 1
  82.   1 -2 1
  83.   0 1
  84.   -1 2 1
  85.  
  86.   ans = 1.3333333333
  87.  */
  88.  
  89. inline double count_cube_eq(double v, double a, double b, double c)
  90. {
  91.     return v * v * v * a + v * v * b + v * c;
  92. }
  93.  
  94. vector<double> find_roots(double a, double b, double c)
  95. {
  96.     vector<double> ret;
  97.  
  98.     double D = b * b - 4 * a * c;
  99.     if (D > 0)
  100.     {
  101.         double x1 = (-b + sqrt(D)) / (2 * a);
  102.         double x2 = (-b - sqrt(D)) / (2 * a);
  103.         ret.push_back(x1);
  104.         ret.push_back(x2);
  105.     } else if (D == 0)
  106.     {
  107.         double x = (-b + sqrt(D)) / (2 * a);
  108.         ret.push_back(x);
  109.     }
  110.     return ret;
  111. }
  112.  
  113. //ad, bd, cd == f - g
  114. ld count_section(double l, double r, double ad, double bd, double cd)
  115. {
  116.     ld area = 0;
  117.     vector<double> roots;
  118.     if (ad != 0)
  119.     {
  120.         roots = find_roots(ad, bd, cd);
  121.     } else
  122.     {
  123.         //bx + c = 0 => x = -c / b
  124.         if (bd != 0)
  125.         {
  126.             roots.push_back(-cd / bd);
  127.         } else
  128.         {
  129.             //a == 0, b == 0, c ? 0
  130.             if (cd == 0) return 0;
  131.         }
  132.     }
  133.     std::vector<double> roots_from_l_to_r;
  134.     std::copy_if(roots.begin(), roots.end(), std::back_inserter(roots_from_l_to_r), [l, r](double a)
  135.     {
  136.         return a > l && a < r;
  137.     });
  138.  
  139.     roots_from_l_to_r.insert(roots_from_l_to_r.begin(), l);
  140.     roots_from_l_to_r.push_back(r);
  141.  
  142.     double a_integral = ad / 3;
  143.     double b_integral = bd / 2;
  144.     double c_integral = cd;
  145.  
  146.     for (int i = 0; i < roots_from_l_to_r.size() - 1; ++i)
  147.     {
  148.         double A = count_cube_eq(roots_from_l_to_r[i], a_integral, b_integral, c_integral);
  149.         double B = count_cube_eq(roots_from_l_to_r[i + 1], a_integral, b_integral, c_integral);
  150.         area += abs(A - B);
  151.     }
  152.  
  153.     return area;
  154. }
  155.  
  156. int main()
  157. {
  158.     cin.tie(nullptr);
  159.     ios::sync_with_stdio(false);
  160.     cout.precision(numeric_limits<ld>::max_digits10);
  161.  
  162.     int n, m;
  163.     cin >> n >> m;
  164.  
  165.     fill_f(n);
  166.     fill_g(m);
  167.  
  168.     ld area = 0;
  169.  
  170.     int j = 0;
  171.     for (auto &section : f.sections)
  172.     {
  173.         int l = section.open;
  174.         int r = section.close;
  175.         while (g.sections[j].close < r)
  176.         {
  177.             auto &cur = g.sections[j];
  178.             //todo: find area [g.sections[j].open, g.sections[j].close]
  179.             area += count_section(g.sections[j].open, g.sections[j].close,
  180.                                   section.a - cur.a, section.b - cur.b, section.c - cur.c);
  181.  
  182.             j++;
  183.         }
  184.         //todo: find last area [g.sections[j].open, r)
  185.         auto &cur = g.sections[j];
  186.         area += count_section(g.sections[j].open, r,
  187.                               section.a - cur.a, section.b - cur.b, section.c - cur.c);
  188.     }
  189.  
  190.     cout << area;
  191.     return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement