레이팅 미적용무한한 2차원 평면을 빈틈없이 채우는 삼각형 영역들이 있다. 이 테셀레이션은 다음과 같이 정의된다 (이해를 돕기 위해 그림을 참고하라).
- 오일러 공식에 따르면 실수 \(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\)개의 쌍별 거리의 합을 출력하시오.
문제 제공: Benjamin Qi
채점 방식
- 입력 2-5: \(N\le 10\), \(0\le x,y<5\)
- 입력 6-13: \(N\le 10\)
- 입력 14-21: \(T=1\)
문제 제공: Benjamin Qi
첫째 줄에 독립적인 테스트의 수 \(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 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