[UVA] 11012 - Cosmic Cabbages
Problem A
Cosmic Cabbages
Input: Standard Input
Output: Standard Output
| CABBAGE, n. |
Ambrose Bierce
Scientistsfrom the planet Zeelich have figured out a way togrow cabbages in space. They have constructed a huge 3-dimensional steel gridupon which they plant said cabbages. Each cabbage is attached to a corner inthe grid, where 6 steel cables meet and is assigned Cartesian coordinates. Acosmic ant wants to crawl from cabbage X to cabbage Y along the cables thatmake the grid. The cosmic ant always chooses the shortest possible path alongthe grid lines while going from cabbage X to cabbage Y. This distance is calledthe cosmic distance between two cabbages. Given a collection of cabbages whatis the maximum distance between any two of the cabbages?
Input
The first line of input gives thenumber of cases, N (0<N<21). N test cases follow. Each onestarts with a line containing n (2<=n<=105).The next n lines will each give the 3-dimensional coordinates of acosmic cabbage (integers in the range [-108, 108]).
Output
For each testcase, output one line containing "Case #x:" followed by thelargest cosmic distance between cabbages X and Y, out of all possible choicesof X and Y.
Sample Input Output forSample 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
|
Problem setter: Igor Naverniouk,EPS
Special Thanks: Shahriar Manzoor, EPS
I likedthis problem so much that I said to myself “If I were the problem setter ofthis problem?”
-ShahriarManzoor
找一對曼哈頓距離最大的值
題目解法：
|xi-xj|+|yi-yj|+|zi-zj| = d
討論一下正負號, 只會有 8 種可能, 考慮鏡射的情況只剩下 4 種
(+++, ++-, +-+, +--)
+++: (xi+yi+zi)-(xj+yj+zj) => 找一個最大值減去最小值
++-: (xi+yi-zi)-(xj+yj-zj)
+-+: (xi-yi+zi)-(xj-yj+zj)
+--: (xi-yi-zi)-(xj-yj-zj)
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int x[100000], y[100000], z[100000];
int main() {
int testcase, cases = 0;
int n, i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d %d %d", &x[i], &y[i], &z[i]);
int ret = 0;
int mx1 = -0xfffffff, mn1 = 0xffffff;
int mx2 = -0xfffffff, mn2 = 0xffffff;
int mx3 = -0xfffffff, mn3 = 0xffffff;
int mx4 = -0xfffffff, mn4 = 0xffffff;
for(i = 0; i < n; i++) {
mx1 = max(mx1, x[i]+y[i]+z[i]);
mn1 = min(mn1, x[i]+y[i]+z[i]);
mx2 = max(mx2, x[i]+y[i]-z[i]);
mn2 = min(mn2, x[i]+y[i]-z[i]);
mx3 = max(mx3, x[i]-y[i]+z[i]);
mn3 = min(mn3, x[i]-y[i]+z[i]);
mx4 = max(mx4, x[i]-y[i]-z[i]);
mn4 = min(mn4, x[i]-y[i]-z[i]);
}
ret = max(ret, mx1-mn1);
ret = max(ret, mx2-mn2);
ret = max(ret, mx3-mn3);
ret = max(ret, mx4-mn4);
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}