## 464B

Posted on 03 Dec 2014
brute force dfs

### 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;
}