URAL - 1828 Approximation by a Progression(最小二乘法)

URAL - 1828 Approximation by a Progression(最小二乘法)

Approximation by a Progression Time Limit: 500MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u

Submit Status

Description

Your are given a sequence of integers a₁, …, a_n. Find an arithmetic progression b₁, …, b_n for which the value ∑( a_i ? b_i) ² is minimal. The elements of the progression can be non-integral.

Input

The first line contains the number n of elements in the sequence (2 ≤ n ≤ 10 ⁴). In the second line you are given the integers a₁, …, a_n; their absolute values do not exceed 10 ⁴.

Output

Output two numbers separated with a space: the first term of the required arithmetic progression and its difference, with an absolute or relative error of at most 10 ^?6. It is guaranteed that the answer is unique for all input data.

Sample Input

input output

4
0 6 10 15

0.400 4.900

4
-2 -2 -2 -2

-2 0

arithmetic progression 等差數列的通式an=a1+（n-1)*d，即an=（a1-d）+n*d 是直線方程的形式，而（i，mi）是分布在直線兩邊的點，要求直線的 k=d，b=a1-d，於是想到最小二乘法，對Y=kX+b ， 有 k=（（XY）平--X平*Y平）/（（X^2）平--(X平）^2）， b=Y平--kX平。按公式求就好了。

#include
#include
using namespace std;
const int MAXN = 10005;
double a[MAXN];
int main()
{
	int n;
	while (cin >> n)
	{
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		double xy=0, x=0, y=0, x2=0;
		for (int i = 1; i <= n; i++)
		{
			xy = xy + a[i] * i;
			x = x + i;
			y = y + a[i];
			x2 = x2 + i*i;
		}
		double k = (xy/n -(x/n)*(y/n)) / (x2/n  - (x/n)*(x/n));
		double b = y / n - k*(x / n);
		double a1 = b + k;
		double d = k;
		cout <