import java.io.*;

class SCO11
{ 
  public static double[][]  Lagrange(double xi[],double yi[])
  {
	 int n=xi.length;
     double L[][]=new double[2][n];
     for(int i=0;i<n;i++)
     {L[0][i]=yi[i];
     for(int j=0;j<n;j++)
     {if(i!=j) L[0][i]/=(xi[i]-xi[j]);}
     }
     for(int i=0;i<n;i++)
     {L[1][i]=xi[i];}
     return L;
  }
  
	
  public static double  funcLagrange(double L[][],double x)
  {
	 int n=L[0].length;
     double carpim=1.0;
     double toplam=0;
     for(int i=0;i<n;i++)
     {carpim=L[0][i];
     for(int j=0;j<n;j++)
     {if(i!=j) carpim*=(x-L[1][j]);}
     toplam+=carpim;
     }
     return toplam;
  }
  
 public static double[][]  funcLagrange(double xi[],double yi[],int nLagrange)
 {
    double z[][]=new double[2][nLagrange];
    double xminimum=9.99e50;
    double xmaximum=-9.99e50;
    double Q[][]=Lagrange(xi,yi);	
    double x1=0;      
	      for(int j=0;j<xi.length;j++)
          { if(xi[j]>xmaximum) xmaximum=xi[j];
            if(xi[j]<xminimum) xminimum=xi[j];
          } 
    if(xmaximum==xminimum) {System.out.println("wrong data setdefinition");}                   
    int i=0;
    double dx=(xmaximum-xminimum)/(nLagrange-1);
    for(x1=xminimum;x1<=xmaximum;x1+=dx) {z[0][i]=x1;z[1][i]=funcLagrange(Q,x1);i++;}
    if(x1==0) x1=xi[nLagrange-1]; {z[0][i]=x1;z[1][i]=funcLagrange(Q,x1);}
    return z;
 } 
  
   public static double[][]  Newton(double xi[],double yi[])
  {
	 int n=xi.length;
	 double F[][]=new double[n+1][n];
	 for(int i=0;i<n;i++)
	    F[i][0]=yi[i];	    
     for(int i=1;i<n;i++)
     { for(int j=1;j<=i;j++)
         {F[i][j]=(F[i][j-1]-F[i-1][j-1])/(xi[i]-xi[i-j]);}
     }
     for(int i=0;i<n;i++)
     {F[n][i]=xi[i];}
     //System.out.println(Matrix.toString(F));
     return F;
  }
  
	
  public static double  funcNewton(double F[][],double x)
  {
	 int n=F[0].length;
     double carpim=1.0;
     double toplam=0;
     for(int i=0;i<n;i++)
       {   carpim=F[i][i];
	       for(int j=0;j<=(i-1);j++)
          {carpim*=(x-F[n][j]);}
          toplam+=carpim;
       }
     return toplam; 
  }
  
 public static double[][]  funcNewton(double xi[],double yi[],int nNewton)
 {
    double z[][]=new double[2][nNewton];
    double xminimum=9.99e50;
    double xmaximum=-9.99e50;
    double Q[][]=Newton(xi,yi);	
    double x1=0;      
	      for(int j=0;j<xi.length;j++)
          { if(xi[j]>xmaximum) xmaximum=xi[j];
            if(xi[j]<xminimum) xminimum=xi[j];
          } 
    if(xmaximum==xminimum) {System.out.println("wrong data setdefinition");}                   
    int i=0;
    double dx=(xmaximum-xminimum)/(nNewton-1);
    for(x1=xminimum;x1<=xmaximum;x1+=dx) {z[0][i]=x1;z[1][i]=funcNewton(Q,x1);i++;}
    if(x1==0) x1=xi[nNewton-1]; {z[0][i]=x1;z[1][i]=funcNewton(Q,x1);}
    return z;
 } 
   	 	  
  public static double [] Hermite(double xi[],double fi[],double dfi[])
  {
  //m polinom derecesi	  
  int i,j;
  int m=xi.length; 
  int n=m-1;
  double Q[][]=new double[2*n+2][2*n+2];
  double QQ[]=new double[2*n+2];
  double z[]=new double[2*n+2];
  for(i=0;i<=n;i++)
    {
	z[2*i]=xi[i];
	z[2*i+1]=xi[i];
	Q[2*i][0]=fi[i];
	Q[2*i+1][0]=fi[i];
	Q[2*i+1][1]=dfi[i];
	if(i!=0) { Q[2*i][1]=(Q[2*i][0]-Q[2*i-1][0])/(z[2*i]-z[2*i-1]);}
	}
	for(i=2;i<=(2*n+1);i++)
	   {for(j=2;j<=i;j++){Q[i][j]=(Q[i][j-1]-Q[i-1][j-1])/(z[i]-z[i-j]);}
	   }
	for(i=0;i<=(2*n+1);i++)
	  {QQ[i]=Q[i][i];}   
	//System.out.println(QQ.length+"\n"+Matrix.toStringT(QQ));
	return QQ;	
  }
  
  public static double funcHermite(double QQ[],double xi[],double x)
  {
	  //Hermit polinom
  int i,j;
  int m=QQ.length-1;
  double xx=1;
  double toplam=QQ[0];
  for(i=1;i<m;i+=2)
    {   j=(i-1)/2;
	    xx*=(x-xi[j]);
	    toplam+=QQ[i]*xx;
	    xx*=(x-xi[j]);
	    toplam+=QQ[i+1]*xx;
    }
  return toplam;  	  
  }

 public static double[][] funcHermite(double xi[],double yi[],double dyi[],int nHermite)
 {
    double z[][]=new double[2][nHermite];
    double xminimum=9.99e50;
    double xmaximum=-9.99e50;
    double Q[]=Hermite(xi,yi,dyi);	
    double x1=0;      
	      for(int j=0;j<xi.length;j++)
          { if(xi[j]>xmaximum) xmaximum=xi[j];
            if(xi[j]<xminimum) xminimum=xi[j];
          } 
    if(xmaximum==xminimum) {System.out.println("wrong data setdefinition");}                   
    int i=0;
    double dx=(xmaximum-xminimum)/(nHermite-1);
    for(x1=xminimum;x1<=xmaximum;x1+=dx) {z[0][i]=x1;z[1][i]=funcHermite(Q,xi,x1);i++;}
    if(x1==0) x1=xi[nHermite-1]; {z[0][i]=x1;z[1][i]=funcHermite(Q,xi,x1);}
    return z;
 }   
     
  public static double [] thomas(double a[][],double r[])
  {
  //
  int n=a.length;
  double f[]=new double[n];
  double e[]=new double[n];
  double g[]=new double[n];
  double x[]=new double[n];
  for(int i=0;i<n;i++)     {f[i]=a[i][i];}
  for(int i=0;i<(n-1);i++) {g[i]=a[i][i+1];}
  for(int i=0;i<(n-1);i++) {e[i+1]=a[i+1][i];}
  for(int k=1;k<n;k++)
     {e[k]=e[k]/f[k-1];
      f[k]=f[k]-e[k]*g[k-1];
     }
  for(int k=1;k<n;k++)
     {r[k]=r[k]-e[k]*r[k-1];
     }
  x[n-1]=r[n-1]/f[n-1];   
  for(int k=(n-2);k>=0;k--)
     {x[k]=(r[k]-g[k]*x[k+1])/f[k];}
  return x;      
  }
  
  public static double [] thomas(double f[],double e[],double g[],double r[])
  {
  int n=f.length;
  double x[]=new double[n];
  for(int k=1;k<n;k++)
     {e[k]=e[k]/f[k-1];
      f[k]=f[k]-e[k]*g[k-1];
     }
  for(int k=1;k<n;k++)
     {r[k]=r[k]-e[k]*r[k-1];
     }
  x[n-1]=r[n-1]/f[n-1];   
  for(int k=(n-2);k>=0;k--)
     {x[k]=(r[k]-g[k]*x[k+1])/f[k];}
  return x;      
  }
  
  
  public static double [][] cubic_spline(double xi[],double yi[],double c0,double cn)
  {
  int n=xi.length;
  double h[]=new double[n];
  double w[]=new double[n];
  double f[]=new double[n];
  double e[]=new double[n];
  double g[]=new double[n];
  double d[]=new double[n];
  double x[]=new double[n];
  double S[][]=new double[4][n];
  int k;	  
  for(k=0;k<(n-1);k++)
     {h[k]=xi[k+1]-xi[k];
      w[k]=(yi[k+1]-yi[k])/h[k];      
	 }
  d[0]=c0;
  d[n-1]=cn;
  for(k=1;k<(n-1);k++)
     {d[k]=6.0*(w[k]-w[k-1]);}
  f[0]=1.0;
  f[n-1]=1.0;
  g[0]=0.0;
  g[n-1]=0.0;
  e[0]=0.0;
  e[n-1]=0.0;
  for(k=1;k<(n-1);k++)
  {f[k]=2.0*(h[k]+h[k-1]);e[k]=h[k-1];g[k]=h[k];}
  S[2]=thomas(f,e,g,d);
  S[3]=xi;
  for(k=0;k<(n-1);k++)
    {S[0][k]=(6.*yi[k+1]-h[k]*h[k]*S[2][k+1])/(6.0*h[k]);
     S[1][k]=(6.*yi[k]-h[k]*h[k]*S[2][k])/(6.0*h[k]);
    } 
  return S;    	 	     	 
  }
  
  public static double funcSpline(double S[][],double x)
  {
  int n=S[0].length;
  double xx1=0;
  double xx2=0;
  double y=0;
  double hk=0;
  for(int k=0;k<(n-1);k++)
     {if(S[3][k]<=x && x<=S[3][k+1]) 
      {hk=(S[3][k+1]-S[3][k]);
       xx1=(x-S[3][k]);
       xx2=(S[3][k+1]-x);
       y=S[0][k]*xx1+S[1][k]*xx2+(xx1*xx1*xx1*S[2][k+1]+xx2*xx2*xx2*S[2][k])/(6.0*hk);
       break;
       }
     }
       if(y==0 && S[3][n-2]<=x )
       {    
	   int k=n-2;
	   hk=(S[3][k+1]-S[3][k]);
       xx1=(x-S[3][k]);
       xx2=(S[3][k+1]-x);
       y=S[0][k]*xx1+S[1][k]*xx2+(xx1*xx1*xx1*S[2][k+1]+xx2*xx2*xx2*S[2][k])/(6.0*hk);
       }
  return y;
  }     
  
 public static double[][] funcSpline(double xi[],double yi[],int nSpline)
 {
    double z[][]=new double[2][nSpline];
    double xminimum=9.99e50;
    double xmaximum=-9.99e50;
    double S[][]=cubic_spline(xi,yi,0,0);	
    double x1=0;      
	      for(int j=0;j<xi.length;j++)
          { if(xi[j]>xmaximum) xmaximum=xi[j];
            if(xi[j]<xminimum) xminimum=xi[j];
          } 
    if(xmaximum==xminimum) {System.out.println("wrong data setdefinition");}                   
    int i=0;
    double dx=(xmaximum-xminimum)/(nSpline-1);
    for(x1=xminimum;x1<=xmaximum;x1+=dx) {z[0][i]=x1;z[1][i]=funcSpline(S,x1);i++;}
    if(x1==0) x1=xi[nSpline-1]; {z[0][i]=x1;z[1][i]=funcSpline(S,x1);}
    return z;
 }
     
  public static void main(String args[]) throws IOException
  {
  double x[]={1.3,1.6,1.9};
  double y[]={0.620086,0.4554022,0.281818186};
  double dy[]={-0.5220232,-0.5698959,-0.5811571};
  double z[][]=funcHermite(x,y,dy,7);
  System.out.println("Hermite\n"+Matrix.toStringT(z)); 

  double z1[][]=funcLagrange(x,y,7);
  System.out.println("Lagrange\n"+Matrix.toStringT(z1));   
 
  double z2[][]=funcNewton(x,y,7);
  System.out.println("Newton\n"+Matrix.toStringT(z2));   
  
  double z3[][]=funcSpline(x,y,7);
  System.out.println("Spline \n"+Matrix.toStringT(z3));
  }
}