24h購物| | PChome| 登入
2013-03-26 22:09:13| 人氣1,975| 回應0 | 上一篇 | 下一篇

[UVA][交集] 737 - Gleaming the Cubes

推薦 0 收藏 0 轉貼0 訂閱站台


  Gleaming the Cubes 

As chief engineer of the Starship Interprize, the task of repairing the hyperstellar, cubic, transwarped-out software has fallen on your shoulders. Simply put, you must compute the volume of the intersection of anywhere from 2 to 1000 cubes.

Input and Output 

The input data file consists of several sets of cubes for which the volume of their intersections must be computed. The first line of the data file contains a number (from 2 to 1000) which indicates the number of cubes which follow, one cube per line. Each line which describes a cube contains four integers. The first three integers are the x, y and z coordinates of the corner of a cube, and the fourth integer is the positive distance which the cube extends in each of the three directions (parallel to the x, y, and z axes) from that corner.


Following the data for the first set of cubes will be a number which indicates how many cubes are in a second set, followed by the cube descriptions for the second set, again one per line. Following this will be a third set, and so on. Your program should continue to process sets of cubes, outputting the volume of their intersections to the output file, one set per line, until a zero is read for the number of cubes.


Note that the data file will always contain at least one set of cubes, and every set will contain at least 2 and at most 1000 cubes. For any given set of cubes, the volume of their intersections will not exceed 1,000,000 units.

Sample Input 

2
0 0 0 10
9 1 1 5
3
0 0 0 10
9 1 1 5
8 2 2 3
0

Sample Output 

25
9



Miguel Revilla
2000-08-31
直接取 min 跟 max 就可以了

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
    int n, x, y, z, d;
    while(scanf("%d", &n) == 1 && n) {
        int lx, ly, lz, rx, ry, rz;
        scanf("%d %d %d %d", &x, &y, &z, &d);
        lx = x, ly = y, lz = z;
        rx = x+d, ry = y+d, rz = z+d;
        n--;
        while(n--) {
            scanf("%d %d %d %d", &x, &y, &z, &d);
            lx = max(lx, x);
            ly = max(ly, y);
            lz = max(lz, z);
            rx = min(rx, x+d);
            ry = min(ry, y+d);
            rz = min(rz, z+d);
        }
        long long ans;
        ans = max(0, (rx-lx)*(ry-ly)*(rz-lz));
        printf("%lld\n", ans);
    }
    return 0;
}

台長: Morris
人氣(1,975) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 494 - Kindergarten Counting Game
此分類上一篇:[UVA][中國直式開方、二分、萬進] 10023 - Square root

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文