Readme.md

缺失数据恢复

by Yuxuan Zhou

时间限制: 1000 ms

内存限制: 1024 KB

问题描述

一个系统的n个输入输出对为：（x1, y1）（x2, y2）, ... （xn, yn）(n≥2)，其中xi, yi均为实数。该系统的输出值被输入值所唯一确定，即xi=xj时必有yi=yj。现在小明想根据已知的n个输入输出对，计算出通过这n个点的最小阶次的多项式函数，并利用该函数计算给定的m个系统输入值所对应的系统输出值。请你帮助他完成该程序的设计。

输入格式

输入共n+m+3行：

第一行包含一个整数 n（2 ≤ n ≤ 100），表示提供的输入输出对数目。

第二行包含一个整数 m（1 ≤ m ≤1200000），表示待估计数据点的数量。

第 3到n+2 行共n行，每行包含两个实数 xi 和 yi，分别表示一个已知的系统输入和输出值。

第 n+3到n+m+2 行共m行，每行包含一个实数 x，表示其中一个给定的新系统输入值。

输出格式

输出共m+1行：

第一行输出一个整数r，为通过给定n个点的最小阶次多项式函数的阶数

第2行到第m+1行共m行，每行输出1个实数，依次为估计出的多项式函数 f 在第i个感兴趣系统输入x'i上的取值f(x'i)，输出误差要求控制在1e-6之内。

输入样例

3

1

1 1

2 4

3 9

1.5

输出样例

2

2.25

提示

1. 给定的n个系统输入输出可能有重复情况

2. 考虑到浮点数精度问题，在本题中，两个浮点数差的绝对值小于等于1e-6时可视为为同一个值。