#include using namespace std; const int MAXSIZE=6; const int MAXPOLYS=20; struct poly { int x[MAXSIZE], z[MAXSIZE]; int nVerts; } polys[MAXPOLYS]; int nPoly, nPlane; // // tree node class // class node { public: int size; int polys[MAXPOLYS]; node *left, *right; node() { size = 0; left = right = 0;}; }; node *root; void printTree(node *root) // // print leaves in reverse post-order // { if (root->left == 0 && root->right == 0) { for(int i=0; isize; i++) cout << (char)('A'+root->polys[i]); } else { printTree(root->right); printTree(root->left); } } int func(int x, int z, int x1, int z1, int x2, int z2) // // determine which side of a plane point is // { if ((z1-z2)*x - (x1-x2)*z + (x1*z2-x2*z1) > 0) return 1; else return -1; } bool eyeSide(int eyez, poly p, int x1, int z1, int x2, int z2) // // determine if polygon

is on the same side of plane defined // by , as the eye position at <0,eyez> // // NOTE: need only deal with one point of a polygon, since they // are never split by planes // { int eyeval = func(0, eyez, x1, z1, x2, z2); int polyval = func(p.x[0], p.z[0], x1, z1, x2, z2); return (eyeval*polyval > 0); } void applyPlane(node *root, int x1, int z1, int x2, int z2) // // recursively split leaves (if necessary) using plane defined // by , to partion polygons in each leaf // { if (root->left == 0 && root->right == 0) { node *newleft = new node; node *newright = new node; root->left = newleft; root->right = newright; float zintf = ((float)x2*z1-x1*z2)/(x2-x1); int eyez = (int)(zintf-2); // 2 is arbitrary for(int i=0; isize; i++) { if(eyeSide(eyez, polys[root->polys[i]], x1, z1, x2, z2)) newleft->polys[newleft->size++] = root->polys[i]; else newright->polys[newright->size++] = root->polys[i]; } } else { applyPlane(root->left, x1, z1, x2, z2); applyPlane(root->right, x1, z1, x2, z2); } } void main() { cin >> nPoly; root = new node; root->size = nPoly; // initialize poly info and tree for(int i=0; i> polys[i].nVerts; for(int j=0; j> polys[i].x[j] >> polys[i].z[j]; root->polys[i] = i; } cin >> nPlane; // read in each plane and apply to tree for(i=0; i> x1 >> z1 >> x2 >> z2; applyPlane(root, x1, z1, x2, z2); } printTree(root); cout << endl; }