uva 503 - Parallelepiped walk（几何）

题目链接：uva 503 - Parallelepiped walk

恶心题，将三维转成两维，直线距离最短，WA了一天。假设起点在地面，除了考虑经过0，1个面的可能，还要考虑经过两个面到达的可能。后面提供一个生成数据的代码。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;

struct Point {
	ll x, y;
	Point (ll x = 0, ll y = 0): x(x), y(y) {}
};

ll Dis (Point a, Point b) {
	ll x = a.x - b.x;
	ll y = a.y - b.y;
	return x * x + y * y;
}

ll solve (int L, int W, int H, int x1, int y1, int z1, int x2, int y2, int z2) {
	ll ans = inf;
	if (x2 == 0) {
		ans = min(ans, Dis(Point(x1, y1), Point(-z2, y2)));
		ans = min(ans, Dis(Point(x1, y1), Point(y2-W, z2+W)));
		ans = min(ans, Dis(Point(x1, y1), Point(-y2, -z2)));

		ans = min(ans, Dis(Point(x1, y1), Point(z2-H, 2*W+H-y2)));
		ans = min(ans, Dis(Point(x1, y1), Point(z2-H, -(H+y2))));
	} 
	if (x2 == L) {
		ans = min(ans, Dis(Point(x1, y1), Point(L+z2, y2)));
		ans = min(ans, Dis(Point(x1, y1), Point(L+W-y2, z2+W)));
		ans = min(ans, Dis(Point(x1, y1), Point(L+y2, -z2)));
		
		ans = min(ans, Dis(Point(x1, y1), Point(L+H-z2, -(H+y2))));
		ans = min(ans, Dis(Point(x1, y1), Point(L+H-z2, 2*W+H-y2)));
	}

	if (z2 == 0) {
		ans = min(ans, Dis(Point(x1, y1), Point(x2, y2)));
	}

	if (z2 == H) {

		ans = min(ans, Dis(Point(x1, y1), Point(-(H+x2), y2)));
		ans = min(ans, Dis(Point(x1, y1), Point(-(H+y2), -x2)));
		ans = min(ans, Dis(Point(x1, y1), Point(-(W+H-y2), W+x2)));


		ans = min(ans, Dis(Point(x1, y1), Point(2*L+H-x2, y2)));
		ans = min(ans, Dis(Point(x1, y1), Point(L+W+H-y2, L+W-x2)));
		ans = min(ans, Dis(Point(x1, y1), Point(L+H+y2, x2-L)));

		ans = min(ans, Dis(Point(x1, y1), Point(L+H+x2, 2*W+L-y2)));
		ans = min(ans, Dis(Point(x1, y1), Point(L+H+x2, -(L+y2))));
	}
	return ans;
}

int main () {
	int L, W, H, x1, y1, z1, x2, y2, z2;
	while (scanf("%d%d%d%d%d%d%d%d%d", &L, &W, &H, &x1, &y1, &z1, &x2, &y2, &z2) == 9) {
		ll ans = inf;
		for (int i = 0; i < 2; i++) {
			if (x1 == 0) {
				ans = min(ans, solve(W, H, L, y1, z1, x1, y2, z2, x2));
				ans = min(ans, solve(H, W, L, z1, y1, x1, z2, y2, x2));
			} else if (x1 == L) {
				ans = min(ans, solve(W, H, L, y1, z1, L-x1, y2, z2, L-x2));
				ans = min(ans, solve(H, W, L, z1, y1, L-x1, z2, y2, L-x2));
			} else if (y1 == 0) {
				ans = min(ans, solve(L, H, W, x1, z1, y1, x2, z2, y2));
				ans = min(ans, solve(H, L, W, z1, x1, y1, z2, x2, y2));
			} else if (y1 == W) {
				ans = min(ans, solve(L, H, W, x1, z1, W-y1, x2, z2, W-y2));
				ans = min(ans, solve(H, L, W, z1, x1, W-y1, z2, x2, W-y2));
			} else if (z1 == 0) {
				ans = min(ans, solve(L, W, H, x1, y1, z1, x2, y2, z2));
				ans = min(ans, solve(W, L, H, y1, x1, z1, y2, x2, z2));
			} else if (z1 == H) {
				ans = min(ans, solve(L, W, H, x1, y1, H-z1, x2, y2, H-z2));
				ans = min(ans, solve(W, L, H, y1, x1, H-z1, y2, x2, H-z2));
			}
			swap(x1,x2), swap(y1, y2), swap(z1, z2);
		}
		printf("%lld\n", ans);
	}
	return 0;
}


/* Data */
/*
using namespace std;

const int D = 1000;

int main () {
	int cas = 1000;
	while (cas--) {
		int L[3];
		L[0] = rand() % D + 1, L[1] = rand() % D + 1, L[2] = rand() % D + 1;
		printf("%d %d %d ", L[0], L[1], L[2]);
		for (int i = 0; i < 2; i++) {
			int k = rand() % 3;
			for (int j = 0; j < 3; j++) {
				if (k == j)
					printf("%d ", (cas&1 ? L[j] : 0));
				else
					printf("%d ", rand() % L[j] + 1);
			}
		}
		printf("\n");
	}
	return 0;
}
*/

uva 503 - Parallelepiped walk（几何）

原文：http://blog.csdn.net/keshuai19940722/article/details/47732773