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

using namespace std;

double f(int rzad,vector<double> C,double X)
{
    double wynik;

}

double wspolczynnik_c(vector<double> X, vector<double> Y, int l, int r) {
    if (X.size() == 1) {
        return Y[l];
    } else if (X.size() == 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;
}