#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)
{
    if(X.size() == 1)
    {
        return Y[0];
    }
    else
    if(X.size() == 2)
        {
            return (Y[0] - Y[1])/(X[0] - X[1]);
        }
    else
        {
        vector<double> X1(X.begin(), X.end() - 1);
        vector<double> X2(X.begin() + 1, X.end());
        vector<double> Y1(Y.begin(), Y.end() - 1);
        vector<double> Y2(Y.begin() + 1, Y.end());
        return (wspolczynnik_c(X1,Y1) - wspolczynnik_c(X2,Y2))/(X[0] - X[X.size() - 1]);
    }
}

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);
        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;
}