#include<iostream>
#include<conio.h>
#include<stdio.h>
//using namespace std;

double NewtonInterpolation(int NumberOfSamplingPoints, float *x, float *f, double PointToCalculate, bool check);

int main()
{
    int NumberOfSamplingPoints;
    float *x, *f;
    double PointToCalculate;
    bool check;

    while (true) {
        check = true;
        system("cls");
        std::cout << "Enter no of sample points: ";
        std::cin >> NumberOfSamplingPoints;
        std::cout << "Enter All x with corresponding f(x): (" << NumberOfSamplingPoints << ") " << std::endl;

        x = new float[NumberOfSamplingPoints];
        f = new float[NumberOfSamplingPoints];
        for (int i = 0; i < NumberOfSamplingPoints; i++)
            std::cin >> x[i] >> f[i];
        //std::cout << "Enter x for calculation: ";
        //std::cin >> PointToCalculate;
        for (double i = 0; i < 12.5; i++) {
            PointToCalculate = i / 2;
            std::cout << "The result for x = " << PointToCalculate << " is: " << NewtonInterpolation(NumberOfSamplingPoints, x, f, PointToCalculate, check) << std::endl;
            check = false;
        }
        system("pause");
    }
    std::cin.get();
    std::cin.get();
    delete[] x, f;
    return 0;
}

double NewtonInterpolation(int NumberOfSamplingPoints, float *x, float *f, double PointToCalculate, bool check) {
    int i, j;
    double sum = 0, mult;
    if (check == true) {
        std::cout << "Ilorazy: " << std::endl;
        for (j = 0; j < NumberOfSamplingPoints - 1; j++)
        {
            std::cout << "------" << j+1 << "------" << std::endl;
            for (i = NumberOfSamplingPoints - 1; i > j; i--) {
                f[i] = (f[i] - f[i - 1]) / (x[i] - x[i - j - 1]);
                std::cout << "(" << f[i] << ")" << std::endl;
            }
        }
    }
    for (i = NumberOfSamplingPoints - 1; i >= 0; i--)
    {
        mult = 1;
        for (j = 0; i>j; j++)
            mult *= (PointToCalculate - x[j]);

        mult *= f[j];
        sum += mult;
    }
    return sum;
}