double trooth_interpolate_lagrange(trooth_pair* p, int count, double xval);


typedef struct {
	double x;
	double y;
} trooth_pair;



double trooth_interpolate_lagrange(trooth_pair* p, int count, double xval) {
	// Declare us some vars since we can't assume C99
	double val = 0;
	double top = 1;
	double bot = 1;
	int i,j;
	
	for (i=0; i < count; i++) {
		// Calculate top of L_i
		top=1;
		for (j=0; j < count; j++) {
			if (j != i) {
				top *= (xval-(p[j].x));
			}
		}
		
		// Calculate bottom of L_i
		bot=1;
		for (j=0; j < count; j++) {
			if (j != i) {
				bot *= ((p[i].x) - (p[j].x));
			}
		}
		
		// Finish it
		val+=(p[i].y)*(top/bot);
	}
	
	return val;
}