题目分析
本题要求根据已知的 $n$ 个 $d$ 维向量和它们到某个未知向量的欧几里得距离，重建这个未知向量。这是一个典型的多点定位问题。

关键观察

• 已知 $n$ 个参考点的坐标和到目标点的距离
• 需要求解满足所有距离约束的目标点坐标
• 问题可以转化为求解球面交点问题

---

算法思路

核心思想：球面交点定位 + 高斯消元

1. 问题建模
将每个已知向量 $P_i = (x_{i1}, x_{i2}, \dots, x_{id})$ 和距离 $e_i$ 看作一个球面：

$$(X - P_i)^2 = e_i^2$$

2. 线性化处理
通过两两球面方程相减消去二次项，得到线性方程组。以第一个点为参考：

$$2(P_i - P_0) \cdot X = P_i^2 - P_0^2 + e_0^2 - e_i^2 $$

3. 解空间分析

• 当 $n-1 \geq d$ 时，通常有唯一解
• 当 $n-1 < d$ 时，解空间是一个仿射子空间

---

算法流程详解

步骤1：构建线性方程组

for (i = 1; i < n; i++) {
    a[i - 1][m] = dx[i][m] * dx[i][m] - dx[0][m] * dx[0][m];
    for (j = 0; j < m; j++) {
        a[i - 1][j] = 2.0 * (dx[0][j] - dx[i][j]);
        a[i - 1][m] += dx[0][j] * dx[0][j] - dx[i][j] * dx[i][j];
    }
}

步骤2：坐标平移简化

将坐标系平移到第一个点：

for (i = 0; i < n - 1; i++) {
    for (j = 0; j < m; j++) {
        a[i][m] -= a[i][j] * dx[0][j];
    }
}

步骤3：高斯消元求解

pair<vector<ll>, vector<ll>> seq = gauss(n - 1, m);
vector<ll> ok = seq.F;  // 主元列
vector<ll> fr = seq.S;  // 自由变量列

步骤4：解空间处理

情况1：唯一解

if (fr.empty()) {
    for (i = 0; i < m; i++) {
        printf("%.12lf ", a[i][m] + dx[0][i]);  // 平移回原坐标系
    }
}

情况2：多解情况

构建解空间的基础解系：

// 构建自由变量的基础向量
for (i = 0; i < fr.size(); i++) {
    for (j = 0; j < fr.size(); j++) {
        v[fr[j]][i] = (j == i ? 1 : 0);
    }
    for (j = 0; j < ok.size(); j++) {
        v[ok[j]][i] = -a[j][fr[i]];
    }
}

步骤5：选择满足距离约束的解

在解空间中寻找满足到第一个点距离约束的解：

double dis = sqrt((dx[0][m] * dx[0][m] - dis) / disv);
for (i = 0; i < m; i++) {
    ans[i] += dis * v[i][0];  // 沿基础解系方向调整
}

---

关键技术与优化

1. 数值稳定性

• 使用主元选择的高斯消元法
• 双精度浮点数计算
• 容错阈值 eps = 1e-8

2. 编译器优化

#pragma GCC optimize 系列指令
// 提升计算性能，特别是矩阵运算

3. 解空间完备性处理

• 系统化处理自由变量
• 保证找到满足所有约束的解
• 在多个解中任意输出一个符合条件的解

---

复杂度分析

• 时间复杂度：$O(n^3)$，主要在高斯消元步骤
• 空间复杂度：$O(n^2)$，存储系数矩阵
• 对于 $n, d \leq 500$ 的数据范围完全可行

---

正确性证明

1. 数学模型正确性

• 球面方程相减确实消去二次项，得到线性方程
• 解空间构造符合线性代数理论

2. 边界情况处理

• 唯一解情况直接输出
• 多解情况通过距离约束确定具体解
• 保证输出满足 $10^{-5}$ 精度要求

3. 数值稳定性

• 主元选择避免除零错误
• 双精度计算保证精度

---

样例验证

样例1

输入：2 3
0 0 2.5
3 0 2.5  
1.5 0.5 2.5
输出：1.5 -2

验证：点 $(1.5, -2)$ 到三个已知点的距离均为 $2.5$

样例2

输入：2 2
0 0 2
4 -4 6
输出：1.414213562373 1.414213562373

验证：该点确实满足两个距离约束

---

总结

该算法通过巧妙的数学建模，将几何定位问题转化为线性代数问题，利用高斯消元法系统化求解。算法具有以下优点：

1. 理论完备：基于严格的数学推导
2. 实现稳健：处理各种边界情况
3. 精度保证：满足题目精度要求
4. 效率可行：在数据范围内运行高效

这种基于球面交点的定位方法在传感器网络定位、GPS定位等实际问题中有广泛应用。