All Pairs Shortest Paths
플래티넘 II의견: 0
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.
Problem credits: Benjamin Qi
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
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 10
3
6
12
2
6The 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.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Platinum
평가 및 의견
All Pairs Shortest Paths
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
All Pairs Shortest Paths