UVA – 737 – Gleaming the Cubes – O(N)

#include <iostream>
using namespace std;

#define N 1<<12

struct Point3D {
	int x, y, z;
};

#define MN(x, y)  (y ^ ((x ^ y) & -(x < y)))
#define MX(x, y)  (x ^ ((x ^ y) & -(x < y)))

Point3D minmaxp(Point3D a, Point3D b, int mn) {
	if (mn)
		return Point3D { MN(a.x, b.x), MN(a.y, b.y), MN(a.z, b.z) };
	return Point3D { MX(a.x, b.x), MX(a.y, b.y), MX(a.z, b.z) };
}

int main() {
	Point3D vi1, vi2, v1, v2;
	int n, s;
	while ((cin >> n) && n) {
		for (int i = 0; i < n; i++) {
			cin >> v1.x >> v1.y >> v1.z >> s;
			v2 = Point3D { v1.x + s, v1.y + s, v1.z + s };
			if (!i)
				vi1 = v1, vi2 = v2;
			vi2 = minmaxp(v2, vi2, 1), vi1 = minmaxp(v1, vi1, 0);
		}
		int v = (vi2.x - vi1.x) * (vi2.y - vi1.y) * (vi2.z - vi1.z);
		cout << max(v, 0) << endl;
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: