[AdditionalFile5631.zip](file://AdditionalFile5631.zip?type=additional_file)

#5631. 「USACO 2026 Third Platinum」All Pairs Shortest Paths

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2026 Third Contest, Platinum Problem 1. All Pairs Shortest Paths

有一堆三角形区域密铺在一个无限大的 $2\text{D}$ 平面上。该密铺的定义如下（请参考图示以更好地理解）：

回想欧拉公式，对于实数 $x$，有 $e^{ix} = \cos(x) + i\sin(x)$。

首先，在复平面上对于所有整数 $x, y$，在 $x + y\exp(\pi i/3)$ 处画一个顶点。

然后，对于上述步骤中每三个能构成边长为 $1$ 的等边三角形的顶点，画出构成其边界的边。此外，在每个三角形的中心画一个顶点，并从三角形中心向其三个外部顶点各画一条边。

给定 $N$ $(2 \le N \le 2 \cdot 10^5)$ 个输入点，每个点都严格位于某个区域内部（即不在任何顶点或边上）。对于任何一对输入点，定义它们之间的距离为：在不经过任何顶点的情况下，从一个点到另一个点的路径所穿过的边的最少数量。

输出所有 $N(N-1)/2$ 对输入点之间距离的总和。

输入格式

输入的第一行包含 $T$ $(T \ge 1)$，表示独立测试用例的数量。每个测试用例的格式如下：

第一行包含 $N$。

接下来的 $N$ 行每行包含三个整数 $x, y$ 和 $z$ $(0 \le x, y < 10^6, 0 \le z < 12)$，代表复平面上位于 $x + y\exp(\pi i/3) + \epsilon \cdot \exp((1 + 2z)\pi i/12)$ 处的一个点（其中 $\epsilon$ 是一个很小的正数）。

保证所有测试用例中 $N$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，在新的一行中输出所有 $N(N-1)/2$ 对距离的总和。

样例

输入

6
2
0 0 0
0 0 0
2
0 0 0
1 1 7
2
0 0 0
0 0 6
3
0 0 1
0 0 5
0 0 9
2
0 2 11
1 1 1
2
2 0 11
1 1 1

输出

0
3
6
12
2
6

第二个测试用例的图示如下：

对于每个 $x \in [-1, 2], y \in [-1, 2]$，位于 $x + y\exp(\pi i/3)$ 的顶点被标记为 $(x, y)$。

在上述顶点以及作为每个等边三角形中心的顶点处画有点。

包含 $(x, y, z) = (0, 0, 0)$ 的三角形区域被染成绿色。

包含 $(x, y, z) = (1, 1, 7)$ 的三角形区域被染成蓝色。注意 $15\pi/12 = 225^\circ$。

画出了一个从第一个区域到第二个区域穿过三条边的路径示例。

数据范围与提示

• 测试点 2-5：$N\le 10$, $0\le x,y<5$
• 测试点 6-13：$N\le 10$
• 测试点 14-21：$T=1$

供题：Benjamin Qi