def Lagrange(x, y, n, xi):
#----------------------------------------------------------------------------
# Evaluates the Lagrange interpolating polynomial of n data points at xi
# x[] - x-coordinates of data points
# y[] - y-coordinates of data points
# n - number of data points
# xi - interpolation argument
#----------------------------------------------------------------------------
yi = 0e0
for i in range(0,n):
p = 1e0
for j in range(0,n):
if (j != i): p *= (xi - x[j])/(x[i] - x[j])
yi += p * y[i]
return yi
x = [0]*(4)
y = [0]*(4)
x[0]=0
x[1]=1
x[2]=2
x[3]=4
y[0]=1
y[1]=2
y[2]=9
y[3]=65
print Lagrange(x, y, 4, 3.0)
