#include<iostream.h>
#include<fstream.H>
#include<math.h>
#include<stdlib.h>
#define q(a,b) q[(a)*(a+1)/2+b]
#define p(a,b) q[a+1+(b)*(b+1)/2]
ifstream infile("in.txt");
ofstream outfile("out.txt");
double *x,*f,*q,root;
int n,i,j,k;
void indata()
{
infile>>n;
x=new double[n];
f=new double[n];
q=new double[(n+2)*(n+1)/2];
for(i=0;i<=n;i++) infile>>x[i]>>f[i];
infile>>root;
}
void neville()
{
for(i=0;i<=n;i++)
{
q(i,0)=f[i];
for(k=1;k<=i;k++)
q(i,k)=((root-x[i-k])*q(i,k-1)-(root-x[i])*q(i-1,k-1))/(x[i]-x[i-k]);
if(fabs(q(i,i)-q(i-1,i-1))<1e-10)
break;
}
if(i>n) i--;
outfile<<"Neville:"<<q(i,i)<<endl;
}
void aitken()
{
for(i=1;i<=n;i++)
{
p(0,i)=f[0]+(root-x[0])*(f[i]-f[0])/(x[i]-x[0]);
for(j=1;j<i;j++)
p(j,i)=p(j-1,j)+(root-x[j])*(p(j-1,i)-p(j-1,j))/(x[i]-x[j]);
if(fabs(p(i,i)-p(i-1,i-1))<1e-10)
break;
}
if(i>n) i--;
outfile<<endl<<"Aitken:"<<p(i-1,i)<<endl;
}
void mine()
{
q(0,0)=f[0];
for(i=1;i<=n;i++)
{ q(i,0)=f[i];
q(i,1)=1/(x[0]-x[i])*((root-x[i])*f[0]-(root-x[0])*f[i]);
for(k=2;k<=i;k++)
q(i,k)=-1/(x[i-k+1]-x[i])*((root-x[i-k+1])*q(i,k-1)-(root-x[i])*q(i-1,k-1));
if(fabs(q(i,i)-q(i-1,i-1))<1e-10)
break;
}
if(i>n) i--;
outfile<<endl<<"mine:"<<q(i,i)<<endl;
}
int main()
{
indata();
neville();
aitken();
mine();
return 0;
}
input===============
4
-2 0.04
-1 0.2
0 1
1 5
2 25
0.5
output==============
Neville:2.04
Aitken:2.04
mine:2.04
