题意
求给定的n个长方体,求这n个长方体覆盖的体积
思路
思路来源于求n条线段交集。我们可以把每一个长方体看成用三条线替换,从而我们就可以把n个长方体的三条线放到三个桶里面,然后在3个桶里面求出线段交集。答案就是3个交集长度的乘积。
那我们怎样求n个线段的交,很简单的。把n个线段的两个端点分成左右端点,然后加进两个桶,然后取两个桶的一个最大值,一个最小值。
AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x_max, x_min, y_max, y_min, z_max, z_min;
int main(){
    int t, kase = 0;
    scanf("%d", &t);
    while(t--){
	int n;
	x_max = y_max = z_max = 0;
	x_min = y_min = z_min = 1005;
	scanf("%d", &n);
	int x1, y1, z1, x2, y2, z2;
	while(n--){
		scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
		x_max = max(x_max, x1);
		y_max = max(y_max, y1);
		z_max = max(z_max, z1);
		x_min = min(x_min, x2);
		y_min = min(y_min, y2);
		z_min = min(z_min, z2);
		//cout << x_min << " " << y_min << " " << z_min << endl;
	}
	int x_len = x_min - x_max;
	int y_len = y_min - y_max;
	int z_len = z_min - z_max;
	int ans;
	if(x_len < 0 || y_len < 0 || z_len < 0) ans = 0;
	else{
		ans = x_len * y_len * z_len;
	}
	printf("Case %d: %d\n", ++kase, ans);
    }
    return 0;
}