407940: GYM102946 G Group-Theoretic Machine

Gary the shark loves to play puzzles. One day, he learned about the most famous and mind-bending puzzle ever existed: the Rubik's Cube. The Rubik's Cube is a cube-shaped puzzle toy. Each of its faces is divided into a $$$3 \times 3$$$ grid, where each "slice" can be rotated independently. For a solved Rubik's Cube, every side has a unique color, and its color layout is shown below:

Gary has a Rubik's Cube sitting in his toy box, and he's having a hard time solving it. (This is probably due the fact that, according to scientists, most shark species are color blind.) To solve this problem once and for all, he created the powerful Group-Theoretic Machine.

The Group-Theoretic Machine (GTM) is a special machine that can solve any scrambled Rubik's Cube using group-theoretic algorithms. It has six sensors $$$O, R, W, Y, G, B$$$, which correspond to the colors orange, red, white, yellow, green, and blue respectively. Each sensor is located at a fixed position. To increase the stability of the machine, the sensors are designed so that the segments $$$\overline{OR}$$$, $$$\overline{WY}$$$, and $$$\overline{GB}$$$ are parallel to the $$$x$$$-, $$$y$$$-, and $$$z$$$-axes respectively.

For the machine to work, one should first activate it by placing a solved Rubik's Cube inside, such that each sensor touches a face with the corresponding color (touching that face's boundary also counts). Gary has just received a new Rubik's Cube with a side length of $$$d$$$, and he wonders if it can be used to activate the machine. The cube may be oriented or moved freely.

The first line contains one integer $$$t$$$ denoting the number of test cases. Then $$$t$$$ test cases follow.

In each test case, there are 7 lines. The first line contains an integer $$$d$$$. The remaining 6 lines describe the sensors $$$O, R, W, Y, G, B$$$ respectively. Each of them contains three integers $$$x, y, z$$$ denoting the coordinates of a sensor's location.

Technical specifications:

• $$$1 \le t \le 10^3$$$
• $$$1 \le d \le 10^4$$$
• All coordinates in the input are integers between $$$-10^4$$$ and $$$10^4$$$ (inclusive).
• No two input points in a test case are equal.
• The line segment $$$\overline{OR}$$$ is parallel to the $$$x$$$-axis.
• The line segment $$$\overline{WY}$$$ is parallel to the $$$y$$$-axis.
• The line segment $$$\overline{GB}$$$ is parallel to the $$$z$$$-axis.

For each test case, if the machine cannot be activated with Gary's new cube, print a line containing the string NO.

Otherwise, print the string YES. Consider a placement of the Rubik's Cube that can activate the machine. Let $$$V_1, V_2, \dots, V_8$$$ denote the Rubik's Cube's vertices in the order shown ($$$V_8$$$ is the remaining vertex at the back so cannot be seen here):

Print 8 more lines. The $$$i$$$-th ($$$i=1,2,\dots,8$$$) line should consist of three space-separated real numbers $$$x, y, z$$$ describing the coordinates of $$$V_i$$$ under said placement. If there are multiple answers, output any one of them.

Your answer will be accepted if the cube you output satisfies:

• The length of each edge is in the range $$$(d-10^{-6}, d+10^{-6})$$$.
• For each interior angle $$$\theta$$$ of each face, $$$\cos(\theta)$$$ in the range $$$(-10^{-6}, 10^{-6})$$$.
• For each face, the distance between it and the corresponding sensor is less than $$$10^{-6}$$$.

3
2
-1 0 0
1 0 0
0 -1 0
0 1 0
0 0 -1
0 0 1
5
2 7 8
8 7 8
6 3 8
6 9 8
6 7 4
6 7 10
2
-1 0 0
1 0 0
0 1 0
0 -1 0
0 0 -1
0 0 1

YES
1.000000 1.000000 1.000000
-1.000000 1.000000 1.000000
1.000000 -1.000000 1.000000
-1.000000 -1.000000 1.000000
1.000000 1.000000 -1.000000
-1.000000 1.000000 -1.000000
1.000000 -1.000000 -1.000000
-1.000000 -1.000000 -1.000000
YES
7.666667 8.666667 9.666667
3.500000 10.159407 7.340593
5.340593 4.500000 11.159407
1.173927 5.992740 8.833333
9.159407 6.340593 5.500000
4.992740 7.833333 3.173927
6.833333 2.173927 6.992740
2.666667 3.666667 4.666667
NO

NOTICE: Contrary to what the statement PDF says, the checker on Codeforces does NOT have 256 bits of precision, due to technical issues with the Polygon system. It uses __float128 instead, but this is enough for intended solutions to pass.

The images above are licensed under CC-BY-SA 4.0 and are modified from existing images by other authors. The original files can be found here:

1. 3D Rubik's Cube (CC-BY-SA 4.0): https://commons.wikimedia.org/wiki/File:Solved1.svg
2. Rubik's Cube net (CC0): https://commons.wikimedia.org/wiki/File:Rubik%27s_cube_colors.svg