文件名称：洛谷P4035参考源码
文件大小：1KB
文件格式：CPP
更新时间：2022-01-30 19:53:03
洛谷 高斯消元
思路1（洛谷题解） 设n维球体为α，其半径为r（注意，这是一个设而不求。），其球心X的坐标为(x_1,x_2,…,x_n )。∀A_1,A_2,…,A_(n+1)∈α，点A_i (1≤i≤n+1)坐标为(a_((i,1) ),a_((i,2) ),…,a_((i,n) ) )。由n维球体的定义，得方程组： {█((a_((1,1) )-x_1 )^2+(a_((1,2) )-x_2 )^2+⋯+(a_((1,n) )-x_n )^2=r^2@(a_((2,1) )-x_1 )^2+(a_((2,2) )-x_2 )^2+⋯+(a_((2,n) )-x_n )^2=r^2@⋮@(a_((n+1,1) )-x_1 )^2+(a_((n+1,2) )-x_2 )^2+⋯+(a_((n+1,n) )-x_n )^2=r^2 )┤. 从上往下，将第1个方程与第2个方程相减，将第2个方程与第3个方程相减，……，将第n个方程与第(n+1)个方程相减，得： {█(∑_(i=1)^n▒2(a_((1,i) )-a_((2,i) ) ) x_i=∑_(i=1)^n▒(a_((1,i) )+a_((2,i) ) )(a_((1,i) )-a_((2,i) ) ) @∑_(i=1)^n▒2(a_((2,i) )-a_((3,i) ) ) x_i=∑_(i=1)^n▒(a_((2,i) )+a_((3,i) ) )(a_((2,i) )-a_((3,i) ) ) @⋮@∑_(i=1)^n▒2(a_((n,i) )-a_((n+1,i) ) ) x_i=∑_(i=1)^n▒(a_((n,i) )+a_((n+1,i) ) )(a_((n,i) )-a_((n,i) ) ) )┤. 这是一个线性方程组，其增广矩阵为[■(2(a_((1,1) )-a_((2,1) ) )&⋯&2(a_((1,n) )-a_((2,n) ) )&∑_(i=1)^n▒(a_((1,i) )+a_((2,i) ) )(a_((1,i) )-a_((2,i) ) ) @⋮&⋱&⋮&⋮@2(a_((n,1) )-a_((n+1,1) ) )&⋯&2(a_((n,n) )-a_((n+1,n) ) )&∑_(i=1)^n▒(a_((n,i) )+a_((n+1,i) ) )(a_((n,i) )-a_((n+1,i) ) ) )]，可用列主元高斯消元法求得其解。 思路2 n(n∈N_+ )维空间中到两个互不重合的点的距离相等的点的集合叫做这两个点的垂直平分图形。 求n维空间中两点的垂直平分图形的方程的基本思路： 设点A坐标为(a_1,a_2,…,a_n ),点B的坐标为(b_1,b_2,…,b_n )，A≠B，它们的垂直平分图形为β。取∀X∈β，其坐标为(x_1,x_2,…,x_n )。 由垂直平分图形的意义，得： |AX|=|BX|⇔|AX|^2=|BX|^2⇔∑_(i=1)^n▒(a_i-x_i )^2 =∑_(i=1)^n▒(b_i-x_i )^2 ⇔(∑_(i=1)^n▒〖a_i〗^2 )-2(∑_(i=1)^n▒〖a_i x_i 〗)+(∑_(i=1)^n▒〖x_i〗^2 )=(∑_(i=1)^n▒〖b_i〗^2 )-2(∑_(i=1)^n▒〖b_i x_i 〗)+(∑_(i=1)^n▒〖x_i〗^2 )⇔∑_(i=1)^n▒〖2(a_i-b_i ) x_i 〗=∑_(i=1)^n▒(a_i+b_i )(a_i-b_i ) . 最后出来的这个等式就是垂直平分图形的方程。 回到题目中，对于∀A_1,A_2,…,A_(n+1)∈α，取A_1,A_2为一对，A_2,A_3为一对，……，A_n,A_(n+1)为一对代入垂直平分图形的方程中，惊奇地发现得到的线性方程组与思路1中相同，接下来的解法也相同。