Output

For each test case, output one line containing "Case #x:" followed by the largest cosmic distance between cabbages X and Y, out of all possible choices of X and Y.

Sample Input Output for Sample Input

4

2

1 1 1

2 2 2

3

0 0 0

0 0 1

1 1 0

4

0 1 2

3 4 5

6 7 8

9 10 11

6

0 0 0

1 1 1

2 2 2

0 0 1

1 0 0

0 1 0

Case #1: 3

Case #2: 3

Case #3: 27

Case #4: 6

題意：給定n個三維坐標點，求兩兩最大曼哈頓距離。

思路：直接枚舉O（n^2）不可行，那麼換個方法：列出公式 d = |x1 - x2| + |y1 - y2| + |z1 - z2|。對應8種情況這裡不一一列舉，就舉其中x1 - x2 + y1 - y2 + z1 - z2.。轉換為(x1 + y1 + z1) - (x2 + y2 + z2)其他同理。發現只要前面盡可能大，後面盡可能小，出來的曼哈頓距離必然最大，那麼對應8種情況，每種對於每個點都枚舉過去，保存下所有點中x +|- y +|- z 最大和最小的值，最大的作為減數，最小最為被減數，然後對應8種情況中求出最大的即可。

代碼：

#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)

const int N = 100005;

int t, n;
struct Point {
	int v[3];
}p[N];

void init() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d%d", &p[i].v[0], &p[i].v[1], &p[i].v[2]);
}

int solve() {
	int ans = 0;
	for (int i = 0; i < (1<<3); i++) {
		int Min = INF, Max = -INF;
		for (int j = 0; j < n; j ++) {
			int sum = 0;
			for (int k = 2; k >= 0; k--) {
				if (i&(1<