Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#include "bits/stdc++.h"
- #include <iostream>
- #include <vector>
- #include <iomanip>
- #include <limits>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<ll, ll> pll;
- typedef pair<ld, ld> pld;
- typedef pair<int, int> pii;
- #define FOR(i, n) for (int i = 0; i < n; i++)
- #define PI acos(-1)
- struct fun
- {
- struct section
- {
- //y = ax2 + bx + c
- int open, close, a, b, c;
- };
- vector<section> sections;
- } f, g;
- void fill_f(int n)
- {
- f.sections.resize(static_cast<size_t>(n));
- FOR(i, n + 1)
- {
- int li;
- cin >> li;
- f.sections[i].open = li;
- if (i - 1 >= 0) f.sections[i - 1].close = li;
- }
- FOR(i, n)
- {
- int a, b, c;
- cin >> a >> b >> c;
- f.sections[i].a = a;
- f.sections[i].b = b;
- f.sections[i].c = c;
- }
- }
- void fill_g(int m)
- {
- g.sections.resize(static_cast<size_t>(m));
- FOR(i, m + 1)
- {
- int ri;
- cin >> ri;
- g.sections[i].open = ri;
- if (i - 1 >= 0) g.sections[i - 1].close = ri;
- }
- FOR(i, m)
- {
- int a, b, c;
- cin >> a >> b >> c;
- g.sections[i].a = a;
- g.sections[i].b = b;
- g.sections[i].c = c;
- }
- }
- /**
- 1 1
- 0 1
- 0 0 1
- 0 1
- 0 0 2
- ans = 1.0000000000
- 1 1
- 0 1
- 1 -2 1
- 0 1
- -1 2 1
- ans = 1.3333333333
- */
- inline double count_cube_eq(double v, double a, double b, double c)
- {
- return v * v * v * a + v * v * b + v * c;
- }
- vector<double> find_roots(double a, double b, double c)
- {
- vector<double> ret;
- double D = b * b - 4 * a * c;
- if (D > 0)
- {
- double x1 = (-b + sqrt(D)) / (2 * a);
- double x2 = (-b - sqrt(D)) / (2 * a);
- ret.push_back(x1);
- ret.push_back(x2);
- } else if (D == 0)
- {
- double x = (-b + sqrt(D)) / (2 * a);
- ret.push_back(x);
- }
- return ret;
- }
- //ad, bd, cd == f - g
- ld count_section(double l, double r, double ad, double bd, double cd)
- {
- ld area = 0;
- vector<double> roots;
- if (ad != 0)
- {
- roots = find_roots(ad, bd, cd);
- } else
- {
- //bx + c = 0 => x = -c / b
- if (bd != 0)
- {
- roots.push_back(-cd / bd);
- } else
- {
- //a == 0, b == 0, c ? 0
- if (cd == 0) return 0;
- }
- }
- std::vector<double> roots_from_l_to_r;
- std::copy_if(roots.begin(), roots.end(), std::back_inserter(roots_from_l_to_r), [l, r](double a)
- {
- return a > l && a < r;
- });
- roots_from_l_to_r.insert(roots_from_l_to_r.begin(), l);
- roots_from_l_to_r.push_back(r);
- double a_integral = ad / 3;
- double b_integral = bd / 2;
- double c_integral = cd;
- for (int i = 0; i < roots_from_l_to_r.size() - 1; ++i)
- {
- double A = count_cube_eq(roots_from_l_to_r[i], a_integral, b_integral, c_integral);
- double B = count_cube_eq(roots_from_l_to_r[i + 1], a_integral, b_integral, c_integral);
- area += abs(A - B);
- }
- return area;
- }
- int main()
- {
- cin.tie(nullptr);
- ios::sync_with_stdio(false);
- cout.precision(numeric_limits<ld>::max_digits10);
- int n, m;
- cin >> n >> m;
- fill_f(n);
- fill_g(m);
- ld area = 0;
- int j = 0;
- for (auto §ion : f.sections)
- {
- int l = section.open;
- int r = section.close;
- while (g.sections[j].close < r)
- {
- auto &cur = g.sections[j];
- //todo: find area [g.sections[j].open, g.sections[j].close]
- area += count_section(g.sections[j].open, g.sections[j].close,
- section.a - cur.a, section.b - cur.b, section.c - cur.c);
- j++;
- }
- //todo: find last area [g.sections[j].open, r)
- auto &cur = g.sections[j];
- area += count_section(g.sections[j].open, r,
- section.a - cur.a, section.b - cur.b, section.c - cur.c);
- }
- cout << area;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement