#include <iostream>

using namespace std;

struct wezel
{
    int x, y;
};

wezel* wprowadzanie_danych(int n, int &arg)
{
    wezel* tab = new wezel[n];
    int i, j, k, x=0;

        cout << "Wprowadz x0: ";
        cin >> tab[0].x;
        cout << "\nWprowadz y0: ";
        cin >> tab[0].y;

    for(i=1; i<n; i++)
    {
        do
        {   x=0;
            cout << "\nWprowadz x" << i << ": " <<endl;
            cin >> k;
            if(tab[i-1].x > k)
            {
             x=1;
            }
            else
            {
               for(j=i-1; j>=0; j--)
            {
                if(tab[j].x==k)
                {
                    x=1;
                }
            }
            }
        }while(x==1);

        if(i!=0)
        {
        tab[i].x=k;
        cout << "\nWprowadz y" << i << ": " << endl;
        cin >>tab[i].y;
        }
    }

    cout << "\nPodaj wartosc argumentu x: ";
    cin >> arg;

    while((arg<tab[0].x) || (arg>tab[n-1].x))
    {
        cout << "\nPodany argument nie zawiera sie w przedziale interpolacji. Sprobuj ponownie:" << endl;
        cin >> arg;
    }
    return tab;
}

double Lagrange(wezel* tab, int arg, int n)
{
double S=0, I=1, k, r;
int i, j;
for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        if(i!=j)
        {
            k=1.0*(arg-tab[j].x)/(tab[i].x-tab[j].x);
            I*=k;
        }
        else{}
    }
    r=1.0*tab[i].y;
    S+=r*I;
    I=1;
}
return S;
}
int main()
{
int arg;
cout << "Podaj rozmiar tablicy wezlow: ";
int n, x;
cin >> n;
wezel* tab = new wezel[n];
tab=wprowadzanie_danych(n, x);
cout << "Wartosc wielomianu Lagrange'a w podanym punkcie x wynosi: " << Lagrange(tab, arg, n) << endl;
delete[] tab;
return 0;
}