Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <limits>
- #include <cstdlib>
- using namespace std;
- class cubic_spline
- {
- private:
- // Структура, описывающая сплайн на каждом сегменте сетки
- struct spline_tuple
- {
- double a, b, c, d, x;
- };
- spline_tuple *splines; // Сплайн
- std::size_t n; // Количество узлов сетки
- void free_mem(); // Освобождение памяти
- public:
- cubic_spline(); //конструктор
- ~cubic_spline(); //деструктор
- // Построение сплайна
- // x - узлы сетки, должны быть упорядочены по возрастанию, кратные узлы запрещены
- // y - значения функции в узлах сетки
- // n - количество узлов сетки
- void build_spline(const double *x, const double *y, std::size_t n);
- // Вычисление значения интерполированной функции в произвольной точке
- double f(double x) const;
- };
- cubic_spline::cubic_spline() : splines(NULL)
- {
- }
- cubic_spline::~cubic_spline()
- {
- free_mem();
- }
- void cubic_spline::build_spline(const double *x, const double *y, std::size_t n)
- {
- free_mem();
- this->n = n;
- // Инициализация массива сплайнов
- splines = new spline_tuple[n];
- for (std::size_t i = 0; i < n; ++i)
- {
- splines[i].x = x[i];
- splines[i].a = y[i];
- }
- splines[0].c = 0.;
- // Решение СЛАУ относительно коэффициентов сплайнов c[i] методом прогонки для трехдиагональных матриц
- // Вычисление прогоночных коэффициентов - прямой ход метода прогонки
- double *alpha = new double[n - 1];
- double *beta = new double[n - 1];
- double A, B, C, F, h_i, h_i1, z;
- alpha[0] = beta[0] = 0.;
- for (std::size_t i = 1; i < n - 1; ++i)
- {
- h_i = x[i] - x[i - 1], h_i1 = x[i + 1] - x[i];
- A = h_i;
- C = 2. * (h_i + h_i1);
- B = h_i1;
- F = 6. * ((y[i + 1] - y[i]) / h_i1 - (y[i] - y[i - 1]) / h_i);
- z = (A * alpha[i - 1] + C);
- alpha[i] = -B / z;
- beta[i] = (F - A * beta[i - 1]) / z;
- }
- splines[n - 1].c = (F - A * beta[n - 2]) / (C + A * alpha[n - 2]);
- // Нахождение решения - обратный ход метода прогонки
- for (std::size_t i = n - 2; i > 0; --i)
- splines[i].c = alpha[i] * splines[i + 1].c + beta[i];
- // Освобождение памяти, занимаемой прогоночными коэффициентами
- delete[] beta;
- delete[] alpha;
- // По известным коэффициентам c[i] находим значения b[i] и d[i]
- for (std::size_t i = n - 1; i > 0; --i)
- {
- double h_i = x[i] - x[i - 1];
- splines[i].d = (splines[i].c - splines[i - 1].c) / h_i;
- splines[i].b = h_i * (2. * splines[i].c + splines[i - 1].c) / 6. + (y[i] - y[i - 1]) / h_i;
- }
- }
- double cubic_spline::f(double x) const
- {
- if (!splines)
- return std::numeric_limits<double>::quiet_NaN(); // Если сплайны ещё не построены - возвращаем NaN
- spline_tuple *s;
- if (x <= splines[0].x) // Если x меньше точки сетки x[0] - пользуемся первым эл-том массива
- s = splines + 1;
- else if (x >= splines[n - 1].x) // Если x больше точки сетки x[n - 1] - пользуемся последним эл-том массива
- s = splines + n - 1;
- else // Иначе x лежит между граничными точками сетки - производим бинарный поиск нужного эл-та массива
- {
- std::size_t i = 0, j = n - 1;
- while (i + 1 < j)
- {
- std::size_t k = i + (j - i) / 2;
- if (x <= splines[k].x)
- j = k;
- else
- i = k;
- }
- s = splines + j;
- }
- double dx = (x - s->x);
- return s->a + (s->b + (s->c / 2. + s->d * dx / 6.) * dx) * dx; // Вычисляем значение сплайна в заданной точке.
- }
- void cubic_spline::free_mem()
- {
- delete[] splines;
- splines = NULL;
- }
- int mounth_to_int(string mounth){
- if(mounth == "January") return 1;
- if(mounth == "February" ) return 2;
- if(mounth == "March" ) return 3;
- if(mounth == "April" ) return 4;
- if(mounth == "May" ) return 5;
- if(mounth == "June" ) return 6;
- if(mounth == "July" ) return 7;
- if(mounth == "August" ) return 8;
- if(mounth == "September" ) return 9;
- if(mounth == "October" ) return 10;
- if(mounth == "November" ) return 11;
- return 12;
- }
- int main() {
- /* Enter your code here. Read input from STDIN. Print output to STDOUT */
- int N;
- cin >> N;
- string line;
- vector<vector<string>> splitline(N, vector<string>(4));
- vector<double> mean;
- vector<double> diff;
- vector<double> dates;
- vector<pair<double,int>> miss;
- vector<int> num_miss;
- splitline.resize(N);
- getline(cin, line);
- getline(cin, line);
- for(int i = 0; i < N; i++){
- cin >> splitline[i][0] >> splitline[i][1] >> splitline[i][2] >> splitline[i][3];
- }
- for(int i =0; i < N; i++){
- if(splitline[i][2][0] == 'M' || splitline[i][3][0] == 'M'){
- if(splitline[i][2][0] == 'M') miss.push_back(pair<double,int> (12 * atoi(splitline[i][0].c_str()) + mounth_to_int(splitline[i][1]),2));
- else miss.push_back(pair<double,int> (12 * atoi(splitline[i][0].c_str()) + mounth_to_int(splitline[i][1]),3));
- num_miss.push_back(i);
- }
- else {
- mean.push_back((atof(splitline[i][2].c_str()) + atof(splitline[i][3].c_str()))/2);
- diff.push_back(atof(splitline[i][2].c_str()) - atof(splitline[i][3].c_str() ) );
- dates.push_back(12 * atoi(splitline[i][0].c_str()) + mounth_to_int(splitline[i][1]));
- }
- }
- cubic_spline cubic_mean;
- cubic_spline cubic_diff;;
- cubic_mean.build_spline(dates.data(), mean.data(), mean.size());
- cubic_diff.build_spline(dates.data(), diff.data(), diff.size());
- for(int i = 0; i< miss.size(); i++){
- if(miss[i].second == 2) {
- if(splitline[i][3][0] == 'M'){
- cout << cubic_mean.f(miss[i].first) + cubic_diff.f(miss[i].first)/2 << endl;
- }
- else cout << cubic_mean.f(miss[i].first) + cubic_diff.f(miss[i].first)/2 << endl;
- // else cout << atoi(splitline[i][3].c_str()) + cubic_diff.f(miss[i].first) << endl;
- }
- else cout << cubic_mean.f(miss[i].first) - cubic_diff.f(miss[i].first)/2 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement