#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#define N 1010

typedef struct pt
{
    double x , y;
} pt;

pt a[N];
double A[N];

void gen(int n , double roots[N] , double tmp)
{
    double coeff[N];
    int i , j;
    for(i = 0 ; i<=n ; ++i)
        coeff[i] = 0;
    coeff[n] = 1;
    for(i = 1; i<=n ; ++i)
    {
        for(j = n - i - 1 ; j<n ; ++j)
        {
            coeff[j] = coeff[j] + (-1)*roots[i-1]*coeff[j+1];
        }
    }

    for(i = n ; i>=0 ; --i)
    {
        A[i] += (coeff[i]*tmp);
    }

}
void make_polynomial(int n)
{
    double tmp;
    int i , j , k;
    double roots[N];

    printf("\nP(X) = ");

    for(i = 0 ; i<=n ; ++i)
        A[i] = 0;


    for(i = 1 ; i<=n ; ++i)
    {
        tmp = a[i].y;
        k = 0;
        for(j = 1 ; j<=n ; ++j)
        {
            if(i == j)
                continue;
            tmp = tmp * (1.0 / (a[i].x - a[j].x));
            roots[k++] = a[j].x;
        }
        gen(n-1 , roots , tmp);
    }

    for(i = n-1 ; i>=0 ; --i)
    {
       // if(fabs(A[i]) < 0.0000001)
           // continue;
        if(i == 0)
            printf("(%.2lf)" , A[i]);
        else if(i == 1)
            printf("(%.2lf)*(X) + " , A[i]);
        else
            printf("(%.2lf)*(X^%d) + " , A[i] , i);

    }
    printf("\n");
}

double interpolate(double x , int n)
{
    double res = 0.0 , tmp;
    int i , j;
    for(i = 1 ; i<=n ; ++i)
    {
        tmp = a[i].y;
        for(j = 1 ; j<=n ; ++j)
        {
            if(i == j)
                continue;
            tmp = tmp * ( (x - a[j].x) / (a[i].x - a[j].x) );
        }
        res+=tmp;
    }
    return res;
}
signed main()
{
    int n , i;
    double x;

    printf("\t--Langrange\'s Interpolation--\n\n");

    printf("Enter number of data points: ");
    scanf("%d" , &n);

    printf("\nEnter the data points:\n");
    for(i = 1 ; i<=n ; ++i)
        scanf("%lf %lf" , &a[i].x , &a[i].y);

    make_polynomial(n);

    printf("\n\nEnter value of x: ");
    scanf("%lf" , &x);

    printf("\nP(%.0lf) = %.4lf\n" , x , interpolate(x , n));


    return 0;
}