//Problem G - BSP trees #include struct point{ int x,y; }; struct node{ int shape[20]; node * left; node * right; }; int n; point objects[20]; void printem(int* A, int n) { for(int i=0;i = cross void crossprod(int a1,int a2,int a3,int b1,int b2,int b3, int& c1,int& c2, int& c3) { c1=a2*b3-a3*b2; c2=a3*b1-a1*b3; c3=a1*b2-a2*b1; } //true if (p1,p2) is in front of line (x1,y1)(x2,y2) int InFront(int x1,int y1,int x2,int y2,int P1,int P2) { int L1,L2,L3,A,B,C; double Y; crossprod(x1,y1,1,x2,y2,1,L1,L2,L3); // is line crossprod(L1,L2,L3,1,0,-P1,A,B,C); // is pt of intersection if (C!=0) //lines aren't parallel { Y = (double) B/C; if(Y>m; cin>>objects[i].x>>objects[i].y; for(j=1;j>dummy>>dummy; } } void makechildren(node * v, int x1, int y1, int x2, int y2) { int i,back,front,b[20],f[20],count=0; node * bb; node * ff; for(i=0;ishape[i]==1) count++; back=front=0; if(count>1) //split group { for(i=0;ishape[i]==1) if(InFront(x1,y1,x2,y2,objects[i].x,objects[i].y)) { f[i]=1; front++; } else { b[i]=1; back++; } } if(back>0 && front>0) { bb = new node; ff = new node; for(i=0;ishape[i]=b[i]; ff->shape[i]=f[i]; } bb->left=bb->right=ff->left=ff->right=NULL; v->left=bb; v->right=ff; } } void Process(node* v,int x1,int y1,int x2,int y2) { if(v->left==NULL && v->right==NULL) //leaf { makechildren(v,x1,y1,x2,y2); return; } if(v->left!=NULL) Process(v->left,x1,y1,x2,y2); if(v->right!=NULL) Process(v->right,x1,y1,x2,y2); } void Traverse(node* v) //preorder { if(v==NULL) return; if(v->left==NULL && v->right==NULL) //v a leaf? { for(int i=0;ishape[i]==1) cout<<(char)('A'+i); return; } Traverse(v->left); Traverse(v->right); } void main() { int i,p,x1,y1,x2,y2; node * root; cin>>n; getobjects(n); cin>>p; root=new node; for(i=0;ishape[i]=1; root->left=root->right=NULL; for(i=0;i>x1>>y1>>x2>>y2; //get a line Process(root,x1,y1,x2,y2); //modify tree } Traverse(root); cout<