g.cpp

ACM World Final 2008题目程序代码

#include <cstdio>
#include <cstring>
using namespace std;
const int M=20;

struct polyn
{
	double a[M];
	polyn()
	{
		memset(a,0,sizeof(a));
	}
	bool read()
	{
		int d;
		scanf("%d",&d);
		if(d==0)return false;
		memset(a,0,sizeof(a));
		for(int i=d;i>=0;--i)
			scanf("%lf",&a[i]);
		return true;
	}
	double operator()(double x) const
	{
		double ans=0;
		for(int i=M-1;i>=0;--i)
			ans=ans*x+a[i];
		return ans;
	}
	polyn operator*(const polyn& x) const
	{
		polyn ans;
		for(int i=0;i<M;++i)
			for(int j=0;j<=i;++j)
				ans.a[i]+=a[j]*x.a[i-j];
		return ans;
	}
	polyn in() const
	{
		polyn ans;
		for(int i=1;i<M;++i)
			ans.a[i]=a[i-1]/i;
		return ans;
	}
	double in(double s,double t) const
	{
		polyn p=in();
		return p(t)-p(s);
	}
} p,q;

int main()
{
	for(int te=1;p.read();++te)
	{
		double c;
		scanf("%lf",&c);
		q.a[1]=1;
		q.a[0]=-c;
		double Ap=p.in(-1,c),Aq=q.in(-1,c);
		double Apq=(p*q).in(-1,c),Aqq=(q*q).in(-1,c);
		double Bp=p.in(c, 1),Bq=q.in(c, 1);
		double Bpq=(p*q).in(c, 1),Bqq=(q*q).in(c, 1);
		double gc=2*(Ap+Bp-Aq*Apq/Aqq-Bq*Bpq/Bqq);
		double a1=(Apq-gc*Aq)/Aqq,a0=gc-c*a1;
		double b1=(Bpq-gc*Bq)/Bqq,b0=gc-c*b1;
		printf("Case %d: %.3lf %.3lf %.3lf %.3lf\n",te,a1,a0,b1,b0);
	}
	return 0;
}