P15579 [USACO26FEB] All Pairs Shortest Paths P

你有一堆三角形区域，它们铺满了一个无限的二维平面。该镶嵌的定义如下（参见图示以更好地理解）： - 回忆欧拉公式指出，对于实数 $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$ 个两两距离之和。

第二个测试用例如下所示： - 顶点 $x + y \exp(\pi i / 3)$ 用 $(x, y)$ 标记，其中 $x \in [-1, 2]$，$y \in [-1, 2]$。 - 在上述顶点以及每个等边三角形的中心顶点处绘制点。 - 包含 $(x, y, z) = (0, 0, 0)$ 的三角形区域用绿色高亮。 - 包含 $(x, y, z) = (1, 1, 7)$ 的三角形区域用蓝色高亮。注意 $15\pi / 12 = 225^{\circ}$。 绘制了一条从第一个区域到第二个区域的示例路径，该路径穿过了三条边。 :::align{center}  ::: ### 评分标准 - 输入 2-5：$N \le 10$，$0 \le x, y < 5$ - 输入 6-13：$N \le 10$ - 输入 14-21：$T = 1$ 题目来源：Benjamin Qi 翻译由 DeepSeek 完成