1743.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1743 on 2006-09-03 at 18:20:30 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 2048;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };

int64 f[N/2][N/2];
int n, x[2*N], xn, y[2*N], yn;
int fx[2*N], fy[2*N], fh[N];
bool vst[N/2][N/2];

bool legal(int cx, int cy) { return cx >= 0 && cx < xn && cy >= 0 && cy < yn && !vst[cx][cy]; }
int disperse(int*, int*, int*);
int area(int);
int bfs(int, int, int);

int main()
{
	while(scanf("%d", &n) != EOF && n != 0) {
		for(int i = 0; i < n; i++) scanf("%d %d %d %d %d", fy+2*i, fx+2*i, fy+2*i+1, fx+2*i+1, fh+i);
		int th; scanf("%d", &th);
		xn = disperse(fx, fx+2*n, x)-1; yn = disperse(fy, fy+2*n, y)-1;
		if(xn == 0 || yn == 0) { printf("0\n"); continue; }
		memset(f, 0, sizeof(f));
		for(int i = 0; i < n; i++) {
			if(fx[2*i] == fx[2*i+1]) {
				if(fy[2*i] > fy[2*i+1]) swap(fy[2*i], fy[2*i+1]);
				for(int j = fy[2*i]; j < fy[2*i+1]; j++) {
					if(fx[2*i] != 0) f[fx[2*i]-1][j] |= fh[i];
					if(fx[2*i] != xn) f[fx[2*i]][j] |= fh[i] << 10;
				}
			} else {
				if(fx[2*i] > fx[2*i+1]) swap(fx[2*i], fx[2*i+1]);
				for(int j = fx[2*i]; j < fx[2*i+1]; j++) {
					if(fy[2*i] != yn) f[j][fy[2*i]] |= fh[i] << 20;
					if(fy[2*i] != 0) f[j][fy[2*i]-1] |= (int64)fh[i] << 30;
				}
			}
		}
		printf("%d\n", area(th));
	}
	
	return 0;
}

int disperse(int* b, int* e, int* s)
{
	int en = e-b, dn;
	memcpy(s, b, sizeof(int)*en);
	sort(s, s+en);
	for(int i = dn = 1; i < en; i++)
		if(s[i] != s[i-1]) s[dn++] = s[i];
	for(int* i = b; i != e; i++) *i = lower_bound(s, s+dn, *i)-s;
	return dn;
}
int area(int th)
{
	memset(vst, false, sizeof(vst));
	int a = (x[xn]-x[0])*(y[yn]-y[0]);
	for(int i = 0; i < yn; i++) {
		if((f[xn-1][i]&1023) < th) a -= bfs(xn-1, i, th);
		if(((f[0][i]>>10)&1023) < th) a -= bfs(0, i, th);
	}
	for(int i = 0; i < xn; i++) {
		if(((f[i][0]>>20)&1023) < th) a -= bfs(i, 0, th);
		if(((f[i][yn-1]>>30)&1023) < th) a -= bfs(i, yn-1, th);
	}
	return a;
}
int bfs(int bx, int by, int th)
{
	if(vst[bx][by]) return 0;
	queue<int> Q; Q.push((bx<<10)|by);
	int a = 0; vst[bx][by] = true;
	while(!Q.empty()) {
		int p = Q.front(); Q.pop();
		int px = p>>10, py = p&1023;
		a += (x[px+1]-x[px])*(y[py+1]-y[py]);
		for(int i = 0; i < 4; i++) {
			int cx = px+DIR[i][0], cy = py+DIR[i][1];
			if(!legal(cx, cy) || ((f[px][py]>>(i*10))&1023) >= th) continue;
			vst[cx][cy] = true; Q.push((cx<<10)|cy);
		}
	}
	return a;
}