UVA 11012 - Cosmic Cabbages（枚举技巧） - c++编程基础

Problem A
Cosmic Cabbages
Input: Standard Input

Output: Standard Output

CABBAGE, n.
A familiar kitchen-garden vegetable about
as large and wise as a man's head.

Ambrose Bierce

Scientists from the planet Zeelich have figured out a way to grow cabbages in space. They have constructed a huge 3-dimensional steel grid upon which they plant said cabbages. Each cabbage is attached to a corner in the grid, where 6 steel cables meet and is assigned Cartesian coordinates. A cosmic ant wants to crawl from cabbage X to cabbage Y along the cables that make the grid. The cosmic ant always chooses the shortest possible path along the grid lines while going from cabbage X to cabbage Y. This distance is called the cosmic distance between two cabbages. Given a collection of cabbages what is the maximum distance between any two of the cabbages

Input

The first line of input gives the number of cases, N (0 . N test cases follow. Each one starts with a line containing n (2<= n<=10 ⁵). The next n lines will each give the 3-dimensional coordinates of a cosmic cabbage (integers in the range [-10 ⁸, 10 ⁸]).

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<