//アキマ(秋間 浩)の補間法

#define MAX 32

class akima{
	double x[MAX],f[MAX];
	int N;		//ユーザーが設定した分点の数
	double zet(double d);
	double pow(double base,int n);
	double m(int j);
	double t(int j);
	double h(int j);
	double a(int j,int k);
	double P(int j,double xx);
	double A(int k,double xx,int n);
	double q(double xx,int n);
	void swap(double *x,double *y);
	void sort();
	void add();
public:
	void set(double px[],double pf[],int n);
	void set(int px[],int pf[],int n);
	double hokan(double xx);
};

double akima::zet(double d)		//絶対値(zettaichi)
{
	return (d<0)?d*(-1):d;
}

double akima::pow(double base,int n)
{
	double d=1;
	for(int i=0;i<n;i++)
		d*=base;
	return d;
}

double akima::m(int j)
{
	return (f[j+1]-f[j]) / (x[j+1]-x[j]);
}

double akima::t(int j)
{
	double d=zet(m(j+1)-m(j))+zet(m(j-1)-m(j-2));
	if(d)		//d!=0
		return (zet(m(j+1)-m(j))*m(j-1)+zet(m(j-1)-m(j-2))*m(j)) / d;
	else		//d==0
		return (m(j-1)+m(j)) / 2;
}

double akima::h(int j)
{
	return x[j+1]-x[j];
}

double akima::a(int j,int k)
{
	switch(k)
	{
		case 0:		return f[j];
		case 1:		return t(j);
		case 2:		return (3*m(j)-2*t(j)-t(j+1)) / h(j);
		case 3:		return (t(j)+t(j+1)-2*m(j)) / pow(h(j),2);
	}
	return -1;		//error
}

double akima::P(int j,double xx)
{
	double d=0;
	for(int i=0;i<=3;i++)
		d+=a(j,i)*pow(xx-x[j],i);		//↓展開式
	return d;
	//a(j,0) + a(j,1)*(xx-x[j]) + a(j,2)*(xx-x[j])*(xx-x[j]) + a(j,3)*(xx-x[j])*(xx-x[j])*(xx-x[j]);
}

double akima::A(int k,double xx,int n)
{
	double d=1;
	for(int i=n-2;i<=n;i++)
		if(i!=k)
			d*=(xx-x[i]) / (x[k]-x[i]);
	return d;
}

double akima::q(double xx,int n)
{
	double d=0;
	for(int k=n-2;k<=n;k++)
		d+=A(k,xx,n)*f[k];
	return d;
}

void akima::swap(double *x,double *y)
{
	double temp=*x;
	*x=*y;
	*y=temp;
}

void akima::sort()		//バブルソート
{
	int k=N+1;
	while(k>=0){
		int i,j;
		for(i=3,j=-1;i<=k;i++)
			if(x[i-1]>x[i]){
				j=i-1;
				swap(&x[i],&x[j]);
				swap(&f[i],&f[j]);
			}
		k=j;
	}
}

void akima::add()
{
	int n=2;
	x[n-2]=x[n]+x[n]-x[n+2];
	x[n-1]=x[n]+x[n+1]-x[n+2];
	f[n-2]=q(x[n-2],n+2);
	f[n-1]=q(x[n-1],n+2);
	
	n=N+1;
	x[n+1]=x[n]+x[n-1]-x[n-2];
	x[n+2]=x[n]+x[n]-x[n-2];
	f[n+1]=q(x[n+1],n);
	f[n+2]=q(x[n+2],n);
}

void akima::set(double px[],double pf[],int n)
{
	for(int i=2;i<n+2;i++){
		x[i]=px[i];
		f[i]=pf[i];
	}
	N=n;
	sort();
	add();

	for(i=0;i<n+4;i++){
		px[i]=x[i];
		pf[i]=f[i];
	}
}

void akima::set(int px[],int pf[],int n)
{
	for(int i=2;i<n+2;i++){
		x[i]=px[i];
		f[i]=pf[i];
	}
	N=n;
	sort();
	add();

	for(i=0;i<n+4;i++){
		px[i]=(int)x[i];
		pf[i]=(int)f[i];
	}
}

double akima::hokan(double xx)
{
	if(xx<x[2])	return q(xx,4);

	for(int j=2;j<=N;j++)
		if(xx>=x[j] && xx<=x[j+1])
			return P(j,xx);

	return q(xx,N+1);		//if(xx>x[N+1])
}