import turtle

def lagrange_interpolation(x, y):
    n = len(x)
    def L(k):
        l = []
        for j in range(n):
            if j != k:
                l.append((x[k] - x[j])/(x[k] - x[j]))
        return l
    
    def P(x_interp):
        p = []
        for i in range(n):
            l = L(i)
            prod = 1
            for j in range(n-1):
                prod *= (x_interp - x[j])*l[j]
            p.append(prod)
        return sum(p)
    
    x_interp = []
    for i in range(x[0], x[-1]+1):
        for j in range(10):
            x_interp.append(i + j/10)
            
    y_interp = [P(x) for x in x_interp]
    return x_interp, y_interp


x = [1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021]
y = [ 85574.2, 90584.8, 91550.1, 94769.2, 98042.1, 96718.8, 98820.3,  99064.6, 102298.0,  111485.4, 118362.0, 126985.7, 143855.7, 146395.7, 153722.5,  166316.3, 189469.5,  180666.5,  189707.0,  249385.9,  327048.6, 341659.7, 162929, 175690.1, 196598.4, 195384, 188073.1, 183976.3]

x_interp, y_interp = lagrange_interpolation(x, y)

# plotar usando turtle
wn = turtle.Screen()
wn.setworldcoordinates(x[0], min(y), x[-1], max(y))
t = turtle.Turtle()
t.penup()
t.goto(x[0], y[0])
t.pendown()
for i in range(len(x_interp)):
    t.goto(x_interp[i], y_interp[i])
t.hideturtle()

wn.mainloop()