//============================================================================
// Name        : ej9ps.cpp
// Author      : PC
// Description : Programa para calcular la interpolación de Lagrange 
//               (método para interpolar una serie de N puntos (xi, yi). Datos:
//               Número de puntos N.
//               Puntos a interpolar (x1, y1), (x2, y2),....,(xN, yN).
//               Valor x a interpolar.
// Usa array dinamico de estructuras
//============================================================================

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

struct pto{
	float x;
	float y;
};

float lagrange(int, pto *, float);
void lee_datos(int , pto *);

int main()
{
	pto *ptos=NULL;
	float x;
	int np;
	char resp;

	cout << "Ingresa numero de puntos : ";
	cin >> np ;
	ptos = new pto[np];

	lee_datos(np, ptos);

	do {
		cout << "Ingresa valor x = " ;
		cin >> x;
		cout << "Valor interpolado = " << lagrange(np,ptos,x) << endl;
		cout << "Desea continuar? (s / n): ";
		cin >> resp;
	}
	while (resp == 's');
	cout << "Fin de programa\n";
	return 0;
}

void lee_datos(int np, pto *ptos)
{

	cout << "Ingresa coordenada x y punto " << endl;
	for (int i=0; i < np; i++)
	{
	   cout << (i + 1) << ": ";
	   cin >> ptos[i].x >> ptos[i].y;
	}
}

float lagrange( int np, pto *arr, float x )
{
   int i,j;
   float suma=0;
   float producto;

   for (j=0; j<np;j++)
   {
      producto=1;
      for (i=0;i<np;i++)
         if (i!=j)
             producto *= (x - arr[i].x)/(arr[j].x - arr[i].x);
      suma += producto * arr[j].y;
   }
   return(suma);
}