假设我们设答案坐标(x1,x2,⋯,xn),对于两个点(a1,a2,⋯,an),(b1,b2,⋯,bn)显然有(a1−x1)2+(a2−x2)2+⋯(an−xn)2=(b1−x1)2+(b2−x2)2+⋯(bn−xn)2
即∑ai2+∑2ai×xi+∑xi2=∑bi2+∑2bi×xi+∑xi2
即∑xi×2(ai−bi)=∑ai2−∑bi2。
对相邻的两个点列出如此的方程共有n个,可知一定有解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include <bits/stdc++.h> #define MAXN 105 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^'0'); ch=getchar(); } return x*f; } namespace Gauss{ double c[MAXN][MAXN],ans[MAXN]; inline void gauss(int n){ for (register int i=1;i<=n;++i){ int id=i; for (register int j=i+1;j<=n;++j){ if (fabs(c[j][i])>fabs(c[id][i])) id=j; } if (id!=i) for (register int j=i;j<=n+1;++j) swap(c[i][j],c[id][j]); for (register int j=i+1;j<=n;++j){ double rate=c[j][i]/c[i][i]; for (register int k=i;k<=n+1;++k) c[j][k]-=c[i][k]*rate; } } for (register int i=n;i>=1;--i){ for (register int j=i+1;j<=n;++j){ c[i][n+1]-=c[j][n+1]*c[i][j]; } c[i][n+1]/=c[i][i]; } } } using namespace Gauss; double a[MAXN][MAXN]; int n; int main(){ n=read(); for (register int i=1;i<=n+1;++i){ for (register int j=1;j<=n;++j){ scanf("%lf",&a[i][j]); } } for (register int i=1;i<=n;++i){ for (register int j=1;j<=n;++j) { c[i][j]=2.00*(a[i][j]-a[i+1][j]); c[i][n+1]+=a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j]; } } gauss(n); for (register int i=1;i<=n;++i){ printf("%.3lf ",c[i][n+1]); } }
|