题目描述

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.

输入格式

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$.

输出格式

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

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

提示

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.

:::align{center} :::

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