// INTERPOLATION
// Program 13 : To impliment Lagrange's interpolation formula
// ------------------------------------------------------------------------

#include <stdio.h>
#include <conio.h>

#define MAXITEMS 10

main()
{
	int i,j;		// for loop
	int n;			// no of terms
	double ax[MAXITEMS];
	double ay[MAXITEMS];
	double x, y = 0, m;	// y is f(x)
	
	printf(" Enter no of terms : ");
	scanf("%d", &n);
	
	for( i=0; i<n; i++)
	{
		printf(" Enter x%d : ", i);
		scanf("%lg", &ax[i]);
		
		printf(" Enter the value of f(%lg) : ", ax[i]);
		scanf("%lg", &ay[i]);
	}
	
	printf("\n Enter the value of x for which you want to find f(x) : ");
	scanf("%lg", &x);
	
	for( i=0; i<n; i++)
	{
		m = 1.0;	// multiplier
		
		for( j=0; j<n; j++)
			if( i != j )
				m *= (x - ax[j]) / (ax[i] - ax[j]);
		
		y += m * ay[i];
	}
	
	printf("\n F(%g) = %g", x, y);	
	getch();
}