#include <stdio.h>
#include <conio.h>
#define N 100
/*******************************************/
/***** Lagranges interpolation formula *****/
/*******************************************/
void main()
{
    /*
    y=(x-x2)(x-x3)...(x-xn)/(x1-x2)(x1-x3)...(x1-xn)*y[1]
    +(x-x1)(x-x3)...(x-xn)/(x2-x2)(x2-x3)...(x2-xn)*y[2]
    +...+
    (x-x1)(x-x2)...(x-x(n-1))/(xn-x1)(xn-x2)...(xn-x(n-1))*y[n]
    */
    float x[N]={1,3,13,21};   /* Values of x i's */
    float y[N]={0,1,3,4};        /* Values of x i's */
    int i,j;                    /* loop variable's */
    float res;                  /* result of each sub term */
    float ans=0;                /* Final result */
    float givx=2;               /* Given x for which y is to be determined */
    int n=4;                    /* No of points for interpolation */
    char ch,newx;                 /* Choice inputing variables */
    do
    {
        printf("\nEnter the total number of points for interpolation\n");
        scanf("%d",&n);
        printf("\nEnter the values of x\n");
        for(i=0;i<n;i++)
            scanf("%f",&x[i]);
        printf("\nEnter the values of y\n");
        for(i=0;i<n;i++)
            scanf("%f",&y[i]);
        do
        {
            printf("\nEnter the values of x to find y\n");
            scanf("%f",&givx);
            for(i=0;i<n;i++)
            {
                res=1;
                for(j=0;j<n;j++)
                {
                    if(i==j)
                        continue;
                    res=res*(givx-x[j])/(x[i]-x[j]);
                }
                ans=ans+res*y[i];
            }
            printf("\nanswer = %g\n",ans);
            printf("\nDo you want y for new value of x[y/n]\n");
            newx=(char)getche();
        }while(newx=='Y' || newx=='y');
        printf("\nDo you wish to continue[y/n]\n");
        ch=(char)getche();
    }while(ch=='Y' || ch=='y');
    getch();
}