#include<stdio.h>
#define MAX_N 20
typedef struct tagPOINT
{
double x;
double y;
}POINT;
int main(){
	int n;
	int i,j;
	POINT points[MAX_N+1]; double diff[MAX_N+1];
    double x,tmp,newton=0;
	printf("\nInput n value:");
	scanf("%d",&n);
	if(n>MAX_N)
	{
		printf("The input n is larger then Max_n,please redefine the MAX_N.\n");
		return 1;
	}
	if(n<=0)
	{
       printf("please input a number between 1 and %d.\n", MAX_N );
       return 1;
	   }
	printf("Now input the (x_i,y_i),i=0,...,%d:\n",n);
		for(i=0;i<=n;i++)
			scanf("%lf%lf",&points[i].x,&points[i].y);
		printf("Now input the x value:");
		scanf("%lf",&x);
        for(i=0;i<=n;i++) diff[i]=points[i].y;
		for(i=0;i<n;i++)
		{
			for(j=n;j>i;j--)
			{
				diff[j]=(diff[j-1])/(points[j].x-points[j-1-i].x);
			}
		}
		tmp=1;newton=diff[0];
		for(i=0;i<n;i++)
		{
			tmp=tmp*(x-points[i].x);
			newton=newton+tmp*diff[i+1];
		}
		printf("newton(%f)=%f\n",x,newton);
		return 0;
}