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