#include <iostream>

using namespace std;

const int n=50;

double x[n],a[n],clen[n];

double bod,y;

int pocet,m,r,i,j,k,p,radu;



int main()

{ cout<<" Zadej pocet bodu, maximálne 50: "; cin>>pocet; cout<<endl;



//vypln prvky pole nulami



if (pocet<n+1)  for( i=0;i<n+1;i++) { a[i]=0; x[i]=0;}

m=pocet-1; r=pocet-1;

for (i=0;i<m+1;i++) { cout<<"  Zadej bod: x["<<i<<"] = "; cin>>x[i];

                     cout<<"           f(x["<<i<<"]) = ";cin>>a[i];

                   }



k=1; // dif[0]=a[0];

for (j=r; j>=1;j--){ for (i=n;i>=1;i--) { p=i+k-1; if ((k<=p) &&  (p<=m))   a[p]=(a[p]-a[p-1])/(x[p]-x[p-k]); }



                //  dif[k]=a[k];  z[j]=x[m]-x[m-k];

                    k=k+1;

                         }



clen[0]=a[0]-a[1]*x[0]+a[2]*x[1]*x[0]-a[3]*x[2]*x[1]*x[0]-a[4]*x[3]*x[2]*x[1]*x[0]-a[5]*x[4]*x[3]*x[2]*x[1]*x[0];

clen[1]=a[1]-a[2]*(x[1]+x[0])+a[3]*(x[2]*x[1]+x[2]*x[0]+x[1]*x[0])-a[4]*(x[3]*x[2]*x[1]+x[3]*x[2]*x[0]+x[3]*x[1]*x[0]+x[2]*x[1]*x[0])+a[5]*(x[4]*x[3]*x[2]*x[1]+x[4]*x[3]*x[2]*x[0]+x[4]*x[2]*x[1]*x[0]+x[3]*x[2]*x[1]*x[0]);

clen[2]=a[2]-a[3]*(x[2]+x[1]+x[0])+a[4]*(x[3]*x[2]+x[3]*x[1]+x[2]*x[1]+x[2]*x[1]+x[1]*x[0])-a[5]*(x[4]*x[3]*x[2]+x[4]*x[3]*x[1]+x[4]*x[2]*x[1]+x[4]*x[2]*x[0]+x[4]*x[1]*x[0]+x[3]*x[2]*x[1]+ x[3]*x[2]*x[0]+x[3]*x[1]*x[0]+x[2]*x[1]*x[0]);

clen[3]=a[3]-a[4]*(x[3]+x[2]+x[1]+x[0])+a[5]*(x[4]*x[3]+x[4]*x[2]+x[4]*x[1]+x[4]*x[0]+x[3]*x[2]+x[3]*x[1]+x[3]*x[0]+x[2]*x[1]+x[2]*x[0]+x[1]*x[0]);

clen[4]=a[4]-a[5]*(x[4]+x[3]+x[2]+x[1]+x[0]);

clen[5]=a[5];

cout<<endl<<endl<<endl;

cout<<"   Newtonuv interpolacni polynom: "<<endl;

cout<<"   pomerne diference: "<<endl;

for (i=0; i< pocet;i++) cout<<"   a "<<i<<" = "<<a[i]<<endl<<endl<<endl;

 radu=pocet-1;

cout<<"   Polynom  "<<radu<<". radu:"<<endl<<endl;



cout<<"   N"<<pocet-1<<"(x) = "<<clen[5]<<" *x^5 + "<< clen[4]<<" *x^4 + "<<clen[3]<<" *x^3 + "<<clen[2]<<" *x^2 + "<<clen[1]<<" *x + "<<clen[0]<<endl<<endl;

cout<<"   Vypocet hodnoty f(x) v bode x "<<endl;

cout<<"   Zadani bodu x: "; cin>>bod; cout<<endl;

y=a[0]+a[1]*(bod-x[0])+a[2]*(bod-x[0])*(bod-x[1])+a[3]*(bod-x[0])*(bod-x[1])*(bod-x[2])+a[4]*(bod-x[0])*(bod-x[1])*(bod-x[2])*(bod-x[3])+a[5]*(bod-x[0])*(bod-x[1])*(bod-x[2])*(bod-x[3])*(bod-x[4]);

cout<<"   Hodnota f("<<bod<<") = "<<y<<endl;

return 0;

}