//アキマ(秋間 浩)の補間法　Simple & C Langrage Ver.

#include"Akima(simple).h"		//for MAX

double x[MAX],f[MAX];
int N;		//ユーザーが設定した分点の数

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

double pow(double base,int n)		//base の n 乗を返す
{
	double d=1;
	for(int i=0;i<n;i++)
		d*=base;
	return d;
}

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

double 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 h(int j)
{
	return x[j+1]-x[j];
}

double 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 '\0';		//error
}

double 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 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 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 add()		//区間外の分点を追加
{
	int 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);
	
	n=2;
	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+2);
	f[n-2]=q(x[n-2],n+2);
}

void aki_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;
	add();

	//区間外の分点を元の配列にコピー
	px[0]=x[0];	pf[0]=f[0];		//左外側
	px[1]=x[1];	pf[1]=f[1];		//左内側
	px[n+2]=x[n+2];	pf[n+2]=f[n+2];		//右内側
	px[n+3]=x[n+3];	pf[n+3]=f[n+3];		//右外側
}

double aki_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])
}

/*
難関は公式にはない関数 add() と aki_hokan() だろうか
初めは細かい点に気を遣う必要はない
全ては公式に合わせているにすぎない
値の意味よりも参照する配列の値が存在するかを確認した方が良い
独自仕様としてユーザーが設定した分点は配列の添字２から格納されている事も忘れてはならない
全体を把握できたら細部をチェックしていこう

○問題：MAX の最小値は？
○解答：7
○解説：ユーザーが設定した分点３＋区間外の分点４
*/