//Who: Abdallah Sayyed-Ahmad
//What: Lagrange Interpolation

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int main()
{
    int i, j, k, n, N, flag;
    double x[100], y[100], dx, x0, x1;
    double xx, yy, p;
    double lgamma(double x);

    n = 0;
    flag = 1;
    x0 = 1e16;
    x1 = -1e16;
    N = 1000;//set the number of points you want to sample the estimated function
// Read (x,y) data from a file
    while (scanf("%lf %lf\n", &x[n], &y[n]) > 0)
    {
        if (x[n] < x0)//get the maximum(x1) and minimum(x0) of the x data
            x0 = x[n];
        if (x[n] > x1)
            x1 = x[n];
        n++;
    }

    dx = (x1 - x0) / N;//evaulate the increments in x needed to get N sampling points in the interval (x0,x1)

    for (i = 0; i < N; i++)//loop over all sampling points
    {
        xx = x0 + i * dx;//evaluate the value of x for the ith point
        yy = 0;
        for (j = 0; j < n; j++)//The first sum over data points
        {
            p = 1;
            for (k = 0; k < n; k++)//calculate the product to get the function p
            {
                if (j != k)
                {
                    p = p * (xx - x[k]) / (x[j] - x[k]);
                }
            }
            yy = yy + y[j] * p;//the interpolation sum
        }
        printf("%lf %lf\n", xx, yy);//print out the data
    }

    return 0;
}