题目分析

问题描述

给定二维平面上的 n 个点 $(x_i, y_i)$，对于每个点 $i$，需要计算它到所有其他点的距离之和：

$$s_i = \sum_{j=1}^{n} \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} $$

直接方法的缺陷

最直接的方法是对于每个点 $i$，计算它到其他 n-1 个点的距离，总时间复杂度为 $O(n^2)$。当 $n = 10^5$ 时，这显然不可行。

算法思路

核心思想：随机投影

代码利用了几何随机投影的思想：

1. 将二维点投影到多个随机方向的直线上
2. 在一维直线上，可以通过排序和累加快速计算"投影距离之和"
3. 多个方向的平均值可以很好地近似真实的二维距离之和

数学原理

对于任意两个点 $P_i$ 和 $P_j$，它们在方向向量 $(\cos\theta, \sin\theta)$ 上的投影距离为：

$$\text{proj}_\theta(P_i, P_j) = |(x_i-x_j)\cos\theta + (y_i-y_j)\sin\theta| $$

根据几何关系，二维真实距离与所有方向上的投影距离满足：

$$\text{dist}(P_i, P_j) = \frac{\pi}{2} \cdot \mathbb{E}_\theta[\text{proj}_\theta(P_i, P_j)] $$

这就是代码最后乘以 $\frac{\pi}{2}$ 的原因。

代码详解

1. 数据输入和初始化

scanf("%d", &n);
fo(i, 1, n)scanf("%lf%lf", &a[i], &b[i]);

读入点的数量 n 和每个点的坐标 (a[i], b[i])。

2. 多方向投影

int T = 180;
fu(i, 0, T) {
    ld c = cos(pi / T * i), s = sin(pi / T * i);

选择 180 个均匀分布的方向，每个方向的角度为 $\theta_i = \frac{\pi}{180} \cdot i$。

3. 投影和排序

fo(j, 1, n) {
    v[j] = a[j] * c - b[j] * s;
    w[j] = j;
}
sort(w + 1, w + 1 + n, [&](int x, int y) {
    return v[x] < v[y];
});

将每个点投影到当前方向的直线上，得到一维坐标 v[j]，然后按投影坐标排序。

4. 累加投影距离

// 从左向右累加
ld sm = 0;
fo(j, 2, n) {
    sm += (j - 1) * (v[w[j]] - v[w[j - 1]]);
    ans[w[j]] += sm;
}

// 从右向左累加  
sm = 0;
fd(j, n - 1, 1) {
    sm += (n - j) * (v[w[j + 1]] - v[w[j]]);
    ans[w[j]] += sm;
}

这是算法的关键部分，通过巧妙的累加在 $O(n)$ 时间内计算所有点在当前投影方向上的"投影距离之和"。

累加原理：

• 当点按投影坐标排序后，对于点 $w[j]$，它与左边所有点的投影距离之和可以通过累加得到
• (j-1) * (v[w[j]] - v[w[j-1]]) 表示当前点与前一个点的距离需要被左边所有 j-1 个点累积
• 从两个方向累加以确保对称性

5. 结果计算

fo(i, 1, n)printf("%.6lf\n", ans[i]*pi / T / 2);

将 180 个方向的结果取平均，并乘以 $\frac{\pi}{2}$ 将投影距离转换为真实距离。

算法标签

• 计算几何 (Computational Geometry)

• 近似算法 (Approximation Algorithm)

• 随机算法 (Randomized Algorithm)

• 随机投影 (Random Projection)

• 期望估计 (Expectation Estimation)

• 坐标旋转 (Coordinate Rotation)

• 排序累加 (Sorting and Accumulation)

• 蒙特卡洛方法 (Monte Carlo Method)

• 距离和计算 (Distance Sum Computation)

• 点集处理 (Point Set Processing)

算法优势

1. 高效性：将 $O(n^2)$ 的问题转化为 $O(T \cdot n \log n)$，其中 $T=180$
2. 可扩展性：通过调整 T 可以平衡精度和效率
3. 实用性：对于大规模数据（$n=10^5$）能够在可接受时间内完成计算

应用场景

这种随机投影方法在以下场景中很有用：

• 大规模数据集的相似性分析
• 聚类分析中的距离矩阵计算
• 图形学中的点云处理
• 机器学习中的核方法近似

该算法展示了如何通过概率方法和几何洞察，将复杂的高维计算转化为简单的一维操作，是计算几何中一个优美的范例。