Problem 1. All Pairs Shortest Paths

USACO 2026 Third Contest, Platinum

You have a bunch of triangular regions that tessellate an infinite 2D plane. The tesselation is defined as follows (see the diagram for a better understanding):

• Recall that Euler's formula states that $e^{ix}=\cos (x)+i\sin (x)$ for real $x$. First, draw a vertex at $x+y\exp(\pi i/3)$ on the complex plane for all integers $x,y$.
• Then for every three vertices from the step above forming an equilateral triangle with side length 1, draw the edges forming its border. Additionally, draw a vertex at the center of the triangle and edges from the center of the triangle to each of three outer vertices.

You are given $N$ ($2\le N\le 2\cdot 10^5$) input points, each of which lies strictly within some region (i.e., not on any vertex or edge). For any pair of the input points, define the distance between them to be the smallest number of edges crossed when drawing a path from one point to the other that doesn't pass through any vertex.

Output the sum of all $N(N-1)/2$ pairwise distances between the input points.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$ ($T\ge 1$), the number of independent tests. Each test is specified as follows:

The first line contains $N$.

The next $N$ lines each contain three integers $x$, $y$, and $z$ ($0\le x,y<10^6, 0\le z<12$) representing a point at $x+y\exp(\pi i/3)+ \epsilon\cdot \exp((1+2z)\pi i/12)$ on the complex plane ($\epsilon$ being a small positive number).

It is guaranteed that the sum of $N$ over all tests doesn't exceed $2\cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output the sum of all $N(N-1)/2$ pairwise distances on a new line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
3
6
12
2
6

The second test is illustrated below:

• The vertex at $x+y\exp(\pi i/3)$ is labeled with $(x,y)$ for each $x\in[-1,2], y\in[-1,2]$.
• Dots are drawn at the vertices mentioned above as well as the vertices that are the centers of each equilateral triangle.
• The triangular region containing $(x,y,z)=(0,0,0)$ is highlighted in green.
• The triangular region containing $(x,y,z)=(1,1,7)$ is highlighted in blue. Note that $15\pi/12=225^{\circ}$.
• An example path from the first region to the second crossing three edges is drawn.

SCORING: Inputs 2-5: $N\le 10$, $0\le x,y<5$Inputs 6-13: $N\le 10$Inputs 14-21: $T=1$

Problem credits: Benjamin Qi