464B

Tutorial

We can use the following code to go through all the permutations of an array.

sort(array, array + n);
do
{} while (next_permutation(array, array + n));

Solution

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define zero(x) (((x)>0?(x):-(x))<eps)
#define eps 1.0E-8
#define MAX_POINT_NUM 0
#define D(x)

struct Point
{
    int x, y, z;

    Point()
    {
        x = y = z = 0;
    }

    Point(int x, int y, int z): x(x), y(y), z(z)
    {}

    Point operator - (const Point &a) const
    {
        return Point(x - a.x, y - a.y, z - a.z);
    }

    Point operator + (const Point &a) const
    {
        return Point(x + a.x, y + a.y, z + a.z);
    }

    bool operator == (const Point &a) const
    {
        return x == a.x && y == a.y && z == a.z;
    }
}point[10];

long long dot_product(Point a, Point b)
{
    return 1LL*a.x * b.x + 1LL*a.y * b.y + 1LL*a.z * b.z;
}

void input()
{
    for (int i = 0; i < 8; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        point[i] = Point(a, b, c);
    }
}

long long point_dist(Point a)
{
    return 1LL*a.x * a.x + 1LL*a.y * a.y + 1LL*a.z * a.z;
}

bool perpendicular(Point a, Point b)
{
    return (dot_product(a, b)) == 0;
}

bool exist(Point a)
{
    for (int i = 0; i < 8; i++)
    {
        if (point[i] == a)
        {
            return true;
        }
    }
    return false;
}

bool is_cube()
{
    int num = 0;
    long long min_val = point_dist(point[0] - point[1]);
    long long dist_array[10];
    Point vec[10];
    for (int i = 1; i < 8; i++)
    {
        double temp = point_dist(point[0] - point[i]);
        dist_array[i] = temp;
        if ((temp - min_val) < 0)
        {
            min_val = temp;
        }
    }
    for (int i = 1; i < 8; i++)
    {
        if ((dist_array[i] - min_val) == 0 && !(point[0] == point[i]))
        {
            vec[num++] = point[i] - point[0];
        }
    }
    if (num != 3)
    {
        return false;
    }
    if (!perpendicular(vec[0], vec[1]))
    {
        return false;
    }
    if (!perpendicular(vec[0], vec[2]))
    {
        return false;
    }
    if (!perpendicular(vec[2], vec[1]))
    {
        return false;
    }
    if (!exist(point[0] + vec[0] + vec[1]))
    {
        return false;
    }
    if (!exist(point[0] + vec[0] + vec[2]))
    {
        return false;
    }
    if (!exist(point[0] + vec[2] + vec[1]))
    {
        return false;
    }
    if (!exist(point[0] + vec[0] + vec[1] + vec[2]))
    {
        return false;
    }
    return true;
}

void output()
{
    puts("YES");
    for (int i = 0; i < 8; i++)
    {
        int a = point[i].x;
        int b = point[i].y;
        int c = point[i].z;
        printf("%d %d %d\n", a, b, c);
    }
}

void dfs(int depth)
{
    if (depth == 8)
    {
        if (is_cube())
        {
            output();
            exit(0);
        }
        return;
    }
    int value[10];
    Point temp = point[depth];
    value[0] = point[depth].x;
    value[1] = point[depth].y;
    value[2] = point[depth].z;
    sort(value, value + 3);
    while (true)
    {
        point[depth].x = value[0];
        point[depth].y = value[1];
        point[depth].z = value[2];
        dfs(depth + 1);
        if (!next_permutation(value, value + 3))
        {
            break;
        }
    }
    point[depth] = temp;
}

int main()
{
    input();
    dfs(1);
    puts("NO");
    return 0;
}