1035.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1035 on 2006-02-11 at 09:16:35 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 256;

class Point {
public:
	int x, y, z;
	void make();
};
void Point::make() {
	scanf("%d %d %d", &x, &y, &z);
}

class Surface {
private:
	int cover() const;
public:
	Point v[MAX];
	int vn, area, z;
	bool inner;
	double inx, iny;
	bool make();
	bool contain(double, double) const;
	bool operator <(const Surface&) const;
};
int Surface::cover() const {
	int A = 0, i;
	for(i = 0; i < vn; i++) A += v[i].x*v[i+1].y - v[i+1].x*v[i].y;
	return abs(A)/2;
}
bool Surface::make() {
	scanf("%d", &vn);
	int i; bool valid = true;
	for(i = 0; i < vn; i++) {
		v[i].make();
		if(i == 0) z = v[i].z;
		else if(z != v[i].z) valid = false;
	}
	if(valid) { v[vn] = v[0]; area = cover(); }
	if(valid) {
		inner = false; inx = v[0].x; iny = v[0].y;
		if(contain(inx+0.5, iny+0.5)) inx+=0.5, iny+=0.5;
		else if(contain(inx-0.5, iny+0.5)) inx-=0.5, iny+=0.5;
		else if(contain(inx+0.5, iny-0.5)) inx+=0.5, iny-=0.5;
		else inx-=0.5, iny-=0.5;
	}
	return valid;
}
bool Surface::contain(double x, double y) const {
	int i;
	bool result = false;
	for (i = 0; i < vn; i++) {
		if(v[i].y == v[i+1].y) continue;
		if(x > v[i].x && y > min(v[i].y, v[i+1].y) && y < max(v[i].y, v[i+1].y))
			result = !result;
	}
	return result;
}
bool Surface::operator <(const Surface& s) const {
	return z < s.z;
}

int main()
{
	Surface surface[MAX];
	int t, T, i, j, n;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n); int sn = 0;
		for(i = 0; i < n; i++)
			if(surface[sn].make()) sn++;
		sort(surface, surface+sn);
		for(i = 0; i < sn; i++)
			for(j = i-1; j >= 0; j--)
				if(surface[j].contain(surface[i].inx, surface[i].iny)) 
					{ surface[i].inner = !surface[j].inner; break; }
		int unit = 0, area = surface[0].area;
		for(i = 1; i < sn; i++) {
			unit += area * (surface[i].z - surface[i-1].z);
			if(surface[i].inner) area -= surface[i].area;
			else area += surface[i].area;
		}
		printf("The bulk is composed of %d units.\n", unit);
	}
	
	return 0;
}