using System;

namespace Lagrange_Interpolation
{

    class Program
    {
        class Data
        {
            private static int length = 0;
            public double x, y;
            public Data(double x, double y)
            {
                this.x = x;
                this.y = y;
                length++;
            }
            ~Data()
            {
                length--;
            }
            public static int GetLength()
            {
                return length;
            }
        };
        static double dividedDiff(Data[] f, int n0, int n)
        {
            if (n - n0 < 1)
            {
                Console.WriteLine("Wrong data");
                Environment.Exit(-1);
                return -1;
            }
            else if (n - n0 == 1)
            {
                return (f[n].y - f[n0].y) / (f[n].x - f[n0].x);
            }
            else
            {
                return (dividedDiff(f, n0 + 1, n) - dividedDiff(f, n0, n - 1)) / (f[n].x - f[n0].x);
            }
        }
        static double interpolate(Data[] f, double x0)
        {
            Console.WriteLine("**********************");
            Console.WriteLine("Newton's Interpolation");
            Console.WriteLine("**********************");

            Console.WriteLine($"X0 = {x0}\n");

            double result = 0;
            int n = Data.GetLength();

            double Li = f[0].y;
            for (int i = 0; i < n; i++)
            {
                if (i > 0)
                {
                    Li = dividedDiff(f, 0, i);
                }
                for (int j = 0; j < i; j++)
                {
                    Li *= x0 - f[j].x;
                }
                Console.WriteLine($"Li[{i}] = {Li:F8}");
                result += Li;
            }
            Console.WriteLine();
            return result;
        }
        static void Main(string[] args)
        {

            Console.Write("К-сть точок: ");
            int n = int.Parse(Console.ReadLine());
            if (n < 2)
            {
                Console.WriteLine("Error");
                Environment.Exit(1);
            }
            Data[] f = new Data[n];
            for (int i = 0; i < n; i++)
            {

                Console.WriteLine($"Введiть {i + 1} точку: ");
                string[] c = Console.ReadLine().Split(' ');
                f[i] = new Data(double.Parse(c[0]), double.Parse(c[1]));
            }
            Console.Write("Введiть x0: ");
            double x0 = double.Parse(Console.ReadLine());
            Console.WriteLine($"Value of f({x0}) = {interpolate(f, x0)}");
        }
    }
}