#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

double f(int rzad,vector<double> C,vector<double> X,double x)
{
    double wynik=0
    double
    int k=1,xi=0;
    for(int i=0;i<rzad;i++)
    {
        for(int j=k;j>i;j--)
        {

        }
    }
}

double wspolczynnik_c(vector<double> X, vector<double> Y, int l, int r)
{
    if (r-l == 1)
    {
        return Y[l];
    }
    else
    if (r-l == 2)
    {
        return (Y[l] - Y[r]) / (X[l] - X[r]);
    }
    else
    {
        int l1 = l;
        int r1 = r - 1;
        int l2 = l + 1;
        int r2 = r;
        return (wspolczynnik_c(X, Y, l1, r1) - wspolczynnik_c(X, Y, l2, r2)) / (X[l] - X[r]);
    }
}



int main()
{
    vector<double> X;
    vector<double> Y;
    vector<double> C;
    int rzad,pkt,j,i=0,k=1;
    double a;
    cout << "Podaj ilosc punktow do interpolacji: " << endl;
    cin >> pkt;
    cout << "Podaj zakladany rzad funkcji: " << endl;
    cin >> rzad;
    for(pkt;pkt>0;pkt--)
    {
        cout << "Podaj X: "<<endl;
        cin >> a;
        X.push_back(a);
        cout << "Podaj f(" << X[i] << "): " << endl;
        cin >> a;
        Y.push_back(a);
        i++;
    }
    for(i=0;i<rzad;i++)
    {
        vector<double> X1(X.begin(), X.end() - (i+1));
        vector<double> Y1(Y.begin(), Y.end() - (i+1));
        a=wspolczynnik_c(X1,Y1, 0, X1.size() - 1);
        cout<<a<<endl;
        C.push_back(a);
    }
    cout << "Interpolacja rzedu " << rzad << " dla podanych punktow wyglada nastepujaco: " << endl << C[C.size()-1];
    for(i=0;i<rzad;i++)
    {
        int x=0;
        cout << " + ";
        cout << C[C.size()-(i+2)];
        for(j=k;j>i;j--)
        {
            cout << "(X-" << X[x] << ")";
            x++;
        }
        k+=2;
    }
    return 0;
}