# include <iostream.h>
 # include   <stdlib.h>
 # include   <string.h>
 # include    <stdio.h>
 # include    <conio.h>
 # include     <math.h>

 constint max_size=13;

 int n=0;

 longdouble an[max_size]={0};
 longdouble bn[max_size]={0};
 longdouble cn[max_size]={0};
 longdouble dn[max_size]={0};

 longdouble fx[max_size]={0};
 longdouble xn[max_size]={0};
 
 void show_screen( );
 void clear_screen( );
 void get_input( );
 void generate_natural_cubic_spline( );
 void show_natural_cubic_spline( );

 /*************************************************************************//*************************************************************************///------------------------------  main( )  ------------------------------///*************************************************************************//*************************************************************************/int main( )
    {
       clrscr( );
       textmode(C4350);

       show_screen( );
       get_input( );
       generate_natural_cubic_spline( );
       show_natural_cubic_spline( );

       getch( );
       return 0;
     }

 /*************************************************************************//*************************************************************************///------------------------  Funcion Definitions  ------------------------///*************************************************************************//*************************************************************************//*************************************************************************///--------------------------  show_screen( )  ---------------------------///*************************************************************************/void show_screen( )
    {
       cprintf("\n********************************************************************************");
       cprintf("**************-                                                    -************");
       cprintf("*-------------- ");

       textbackground(1);
       cprintf(" Construction of Natural Cubic Spline Interpolant ");
       textbackground(8);

       cprintf(" ------------*");
       cprintf("*-************-                                                    -**********-*");
       cprintf("*-****************************************************************************-*");

       for(int count=0;count<42;count++)
      cprintf("*-*                                                                          *-*");

       gotoxy(1,46);
       cprintf("*-****************************************************************************-*");
       cprintf("*------------------------------------------------------------------------------*");
       cprintf("********************************************************************************");

       gotoxy(1,2);
    }

 /*************************************************************************///-------------------------  clear_screen( )  ---------------------------///*************************************************************************/void clear_screen( )
    {
       for(int count=0;count<37;count++)
      {
         gotoxy(5,8+count);
         cout<<"                                                                        ";
      }

       gotoxy(1,2);
    }

 /*************************************************************************///-----------------------------  get_input( )  --------------------------///*************************************************************************/void get_input( )
    {
       do
      {
         clear_screen( );

         gotoxy(6,9);
         cout<<"Number of Distinct Data Points :";

         gotoxy(6,10);
         cout<<"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ";

         gotoxy(27,13);
         cout<<"[ min. n = 3  |  max. n = 12 ]";

         gotoxy(6,12);
         cout<<"Enter the max. number of distinct data points = n = ";

         cin>>n;

         if(n<3 || n>12)
        {
           gotoxy(12,25);
           cout<<"Error : Wrong Input. Press <Esc> to exit or any other key";

           gotoxy(12,26);
           cout<<"        to try again.";

           n=int(getche( ));

           if(n==27)
              exit(0);
        }
      }
       while(n<3 || n>12);

       clear_screen( );

       gotoxy(6,9);
       cout<<"Data Points & Values of Function :";

       gotoxy(6,10);
       cout<<"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ";

       gotoxy(25,12);
       cout<<"ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿";

       gotoxy(25,13);
       cout<<"³       x       ³     f(x)      ³";

       gotoxy(25,14);
       cout<<"ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´";

       gotoxy(25,15);
       cout<<"³               ³               ³";

       for(int count_1=0;count_1<n;count_1++)
      {
         gotoxy(25,(wherey( )+1));
         cout<<"³               ³               ³";

         gotoxy(25,(wherey( )+1));
         cout<<"³               ³               ³";
      }

       gotoxy(25,(wherey( )+1));
       cout<<"ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ";

       gotoxy(25,15);

       for(int count_2=0;count_2<n;count_2++)
      {
         gotoxy(25,(wherey( )+1));

         gotoxy(27,wherey( ));
         cin>>xn[count_2];

         gotoxy(43,(wherey( )-1));
         cin>>fx[count_2];
      }

       gotoxy(25,43);
       cout<<"Press any key to continue...";

       getch( );
    }

 /*************************************************************************///-----------------  generate_natural_cubic_spline( )  ------------------///*************************************************************************/void generate_natural_cubic_spline( )
    {
       // set ai=f(xi)     for i=0,1,2,3,...,nfor(int count_1=0;count_1<n;count_1++)
      an[count_1]=fx[count_1];

       longdouble temp_1[max_size]={0};      // hilongdouble temp_2[max_size]={0};      // ailongdouble temp_3[max_size]={0};      // lilongdouble temp_4[max_size]={0};      // uilongdouble temp_5[max_size]={0};      // zi// set hi=x(i+1)-xi     for i=0,1,2,3,...,n-1for(int count_2=0;count_2<(n-1);count_2++)
      temp_1[count_2]=(xn[count_2+1]-xn[count_2]);

       // set ai=(3/hi)*[a(i+1)-ai]-[3/h(i-1)]*[ai-a(i-1)]     for i=1,1,2,3,...,n-1for(int count_3=1;count_3<(n-1);count_3++)
      temp_2[count_3]=(((3/temp_1[count_3])*(an[(count_3+1)]-an[count_3]))-((3/(temp_1[(count_3-1)])*(an[count_3]-an[(count_3-1)]))));

       // set li0=1//     ui0=0//     zi0=0
       temp_3[0]=1;
       temp_4[0]=0;
       temp_5[0]=0;

       // for i=1,1,2,3,...,n-1 ,set//    li=[2*{x(i+1)-x(i-1)}]-[h(i-1)*u(i-1)]//    ui=hi/li//    zi=[ai-{h(i-1)*z(i-1)}]/lifor(int count_4=1;count_4<(n-1);count_4++)
      {
         temp_3[count_4]=((2*(xn[(count_4+1)]-xn[(count_4-1)]))-(temp_1[(count_4-1)]*temp_4[(count_4-1)]));
         temp_4[count_4]=(temp_1[count_4]/temp_3[count_4]);
         temp_5[count_4]=((temp_2[count_4]-(temp_1[(count_4-1)]*temp_5[(count_4-1)]))/temp_3[count_4]);
      }

       // set lin=1//     zin=0//     cn=0
       temp_3[(n-1)]=1;
       temp_5[(n-1)]=0;
       cn[(n-1)]=0;

       // for i=n-1,n-2,...,0   , set//     ci=zi-[ui*c(i+1)]//     bi=[a(i+1)-ai]/[hi-{hi*{c(i+1)+{2*ci}}/3]//     di=[c(i+1)-ci]/[3*hi]for(int count_5=(n-2);count_5>=0;count_5--)
      {
         cn[count_5]=(temp_5[count_5]-(temp_4[count_5]*cn[(count_5+1)]));
         bn[count_5]=(((an[(count_5+1)]-an[count_5])/temp_1[count_5])-((temp_1[count_5]*(cn[(count_5+1)]+(2*cn[count_5])))/3));
         dn[count_5]=((cn[(count_5+1)]-cn[count_5])/(3*temp_1[count_5]));
      }
    }

 /*************************************************************************///--------------------  show_natural_cubic_spline( )  -------------------///*************************************************************************/void show_natural_cubic_spline( )
    {
       clear_screen( );

       gotoxy(6,9);
       cout<<"Natural Cubic Spline :";

       gotoxy(6,10);
       cout<<"ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ";

       gotoxy(10,12);
       cout<<"The required Cubic Polynomials are :";

       for(int count=0;count<(n-1);count++)
      {
         gotoxy(10,(15+(count*2)));
         cout<<"S"<<count<<"(x) =  ";

         longdouble aix=0;
         longdouble bix=0;
         longdouble cix=0;
         longdouble dix=0;

         aix=(an[count]-(bn[count]*xn[count])+(cn[count]*powl(xn[count],2))-(dn[count]*powl(xn[count],3)));
         bix=(bn[count]-(2*cn[count]*xn[count])+(3*dn[count]*powl(xn[count],3)));
         cix=(cn[count]-(3*dn[count]*xn[count]));
         dix=dn[count];

         cout<<aix;

         if(bix>=0)
        cout<<" + ";

         else
        cout<<" - ";

         cout<<fabsl(bix)<<"x";

         if(cix>=0)
        cout<<" + ";

         else
        cout<<" - ";

         cout<<fabsl(cix)<<"x2";

         if(dix>=0)
        cout<<" + ";

         else
        cout<<" - ";

         cout<<fabsl(dix)<<"x3";
      }

       gotoxy(1,2);
    }