#include #include enum { MAX_FACES = 250, MAX_VERTS = 200 }; enum { AXIS_X = 0, AXIS_Y = 1, AXIS_Z = 2 }; class Face { public: int axis, d, n, area; int v[MAX_VERTS][3]; int l1, l2, u1, u2; bool entry; }; int nFaces; Face **faces; int Axis; int min(int a, int b) { if (a < b) return a; else return b; } int IsPtInPoly(Face *f, int x0, int y0, int a1, int a2) { int n = f->n; int x1 = f->v[n - 1][a1], y1 = f->v[n - 1][a2]; int count = 0; for (int i = 0; i < n; i++) { int x2 = f->v[i][a1], y2 = f->v[i][a2]; if (y1 == y2) if ((x1 <= x0 && x0 < x2) || (x2 <= x0 && x0 < x1)) count++; } return (count & 1); } int IsEntryFace(int fi, int minIdx) { int i, j, k, a1, a2; a1 = (Axis + 1) % 3; a2 = (Axis + 2) % 3; Face *f = faces[fi]; // Choose a point on this face. int minY, minWhere, fn = f->n; minY = f->v[0][a2]; minWhere = 0; for (i = 1; i < fn; i++) if (f->v[i][a2] < minY) minY = f->v[i][a2], minWhere = i; j = (minWhere + 1) % fn; if (f->v[i][a2] != minY) j = (minWhere + fn - 1) % fn; int y0 = minY, x0 = min(f->v[i][a1], f->v[j][a1]); for (int oi = fi - 1; oi >= minIdx; oi--) { Face *of = faces[oi]; if (of->d == f->d) continue; if (x0 < of->l1 || y0 < of->l2 || x0 >= of->u1 || y0 >= of->u2) continue; if (IsPtInPoly(of, x0, y0, a1, a2)) return ! of->entry; } return 1; } int FaceArea(Face *f) { int a1 = (f->axis + 1) % 3, a2 = (f->axis + 2) % 3; int area = 0, n = f->n; int x1 = f->v[n - 1][a1], y1 = f->v[n - 1][a2]; for (int i = 0; i < f->n; i++) { int x2 = f->v[i][a1], y2 = f->v[i][a2]; area += (x2 - x1) * (y2 + y1); x1 = x2; y1 = y2; } if (area < 0) area = -area; return area / 2; } int CompareFaces(const void *p1, const void *p2) { Face *f1 = *((Face **) p1); Face *f2 = *((Face **) p2); if (f1->axis != f2->axis) return f1->axis - f2->axis; return f1->d - f2->d; } int main() { int nCases, i, j; cin >> nCases; faces = new Face*[MAX_FACES]; while (nCases-- > 0) { cin >> nFaces; for (i = 0; i < nFaces; i++) { Face *f = new Face; faces[i] = f; cin >> f->n; for (j = 0; j < f->n; j++) cin >> f->v[j][0] >> f->v[j][1] >> f->v[j][2]; if (f->v[0][0] == f->v[1][0] && f->v[1][0] == f->v[2][0]) f->axis = AXIS_X, f->d = f->v[0][0]; else if (f->v[0][1] == f->v[1][1] && f->v[1][1] == f->v[2][1]) f->axis = AXIS_Y, f->d = f->v[0][1]; else // if (f->v[0][2] == f->v[1][2] && f->v[1][2] == f->v[2][2]) f->axis = AXIS_Z, f->d = f->v[0][2]; int a1 = (f->axis + 1) % 3, a2 = (f->axis + 2) % 3; for (j = 0; j < f->n; j++) { if (j == 0 || f->v[j][a1] < f->l1) f->l1 = f->v[j][a1]; if (j == 0 || f->v[j][a2] < f->l2) f->l2 = f->v[j][a2]; if (j == 0 || f->v[j][a1] > f->u1) f->u1 = f->v[j][a1]; if (j == 0 || f->v[j][a2] > f->u2) f->u2 = f->v[j][a2]; } f->area = FaceArea(f); } qsort(faces, nFaces, sizeof(Face *), &CompareFaces); int fa[4]; fa[0] = 0; fa[1] = 0; fa[2] = 0; fa[3] = nFaces; for (i = 0; i < nFaces; i++) { if (fa[1] == 0 || faces[i]->axis == 1) fa[1] = i; if (fa[2] == 0 || faces[i]->axis == 2) fa[2] = i; } Axis = 0; int n = fa[1] - fa[0]; if (n > fa[2] - fa[1]) Axis = 1, n = fa[2] - fa[1]; if (n > fa[3] - fa[2]) Axis = 2; int volume = 0; for (int curFace = fa[Axis]; curFace < fa[Axis + 1]; curFace++) { Face * f = faces[curFace]; if (curFace == fa[Axis]) f->entry = 1; else f->entry = IsEntryFace(curFace, fa[Axis]); if (f->entry) volume += f->area * f->d; else volume -= f->area * f->d; } if (volume < 0) volume = -volume; } return 0; }