当前位置: 首页 > >

【2012中山市选】最大立方体空间(二维线段树)

发布时间:

Description:

给出一个长方体的箱子,还有在箱子里面的N个长方体的盒子,箱子和盒子的各个边都是*行于某个三维坐标轴。现在要求你找出其中最大的立方体空间,输出它的长度。


首先这个空间必须位于箱子里面,而且不能与其它的盒子占的空间冲突。这个空间也必须是各边*行于某个坐标轴。


0<=N<=1000


0<=xi<=Xi<=L<=1000


0<=yi<=Yi<=W<=1000


0<=zi<=Zi<=H<=1000


题解:

显然二分答案ans。


接着可以把边界缩小ans,盒子的左端点也向下移ans位。


那么如果还有空的点,ans就是合法的。


判断是否还有空的点用二维线段树。


因为二位线段树太那个了,所以我不得不把三段式线段树换掉了(Goodbye)。


infleaking说用四分治,我只想骂一句超级难打。


Code:


#include
#include
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int N = 1005, M = N * N;

int n, x, y, z, ans, T;
struct node {
int x, y, z, u, v, w;
int l, r, c, f, g, h;
} a[N];

int final[N], to[N * 2], next[N * 2], fu[N * 2], tot;
void link(int x, int y, int z) {
next[++ tot] = final[x], to[tot] = y, fu[tot] = z, final[x] = tot;
}
void Clear() {
memset(final, 0, sizeof final); memset(next, 0, sizeof next);
tot = 0;
}

int px, py, pl, pr, pc, son[M][4], mi[M], bz[M], t[M], rt, tt;
void can(int i, int c) {if(i) t[i] += c, bz[i] += c;}
void down(int i) {fo(j, 0, 3) can(son[i][j], bz[i]); bz[i] = 0;}
void dg(int &i, int x, int y, int l, int r) {
if(y < x || r < l) return;
if(!i) i = ++ tt;
if(y < px || x > py || r < pl || l > pr) return;
if(x >= px && y <= py && l >= pl && r <= pr) {can(i, pc); return;}
int u = x + y >> 1, v = l + r >> 1;
dg(son[i][0], x, u, l, v), dg(son[i][1], x, u, v + 1, r);
dg(son[i][2], u + 1, y, l, v); dg(son[i][3], u + 1, y, v + 1, r);
down(i);
t[i] = 1e9; fo(j, 0, 3) if(son[i][j]) t[i] = min(t[i], t[son[i][j]]);
}
void add(int X, int Y, int x, int y, int l, int r, int c) {
px = x; py = y; pl = l; pr = r; pc = c;
dg(rt, 0, X, 0, Y);
}

int ple;

bool pd(int m) {
Clear();
rt = tt = 0; memset(son, 0, sizeof son);
memset(t, 0, sizeof t); memset(bz, 0, sizeof bz);
x -= m; y -= m; z -= m;
fo(i, 1, n) {
a[i].l = max(0, a[i].x - m + 1);
a[i].r = max(0, a[i].y - m + 1);
a[i].c = max(0, a[i].z - m + 1);
a[i].f = min(x, a[i].u - 1);
a[i].g = min(y, a[i].v - 1);
a[i].h = min(z, a[i].w - 1);
link(a[i].c, i, 1); link(a[i].h + 1, i, -1);
}
ple = 0;
memset(t, 0, sizeof t); memset(bz, 0, sizeof bz);
fo(i, 0, z + 1) {
for(int j = final[i]; j; j = next[j]) {
int t = to[j];
add(x, y, a[t].l, a[t].f, a[t].r, a[t].g, fu[j]);
}
if(i <= z) ple |= !t[rt];
}
x += m; y += m; z += m;
return ple;
}

int main() {
scanf("%d", &T);
fo(ii, 1, T) {
scanf("%d %d %d %d", &n, &x, &y, &z);
fo(i, 1, n) scanf("%d %d %d %d %d %d", &a[i].x, &a[i].y, &a[i].z, &a[i].u, &a[i].v, &a[i].w);
ans = -1;
for(int l = 0, r = min(x, min(y, z)); l <= r; ) {
int m = l + r >> 1;
if(pd(m)) ans = m, l = m + 1; else r = m - 1;
}
printf("Case %d: %d
", ii, ans);
}
}



友情链接: