#include #include #include #include #define MAX_N 20 #define MAX_M 6 #define MAX_P 10 typedef struct { int x1, z1, x2, z2; } Plane; typedef struct { int m, x[MAX_M], z[MAX_M]; } Object; Object object[MAX_N]; Plane plane[MAX_P]; int n, p; enum { CCW, CW }; int orient(Plane p, int x, int z) { int dx1 = p.x2 - p.x1; int dx2 = x - p.x2; int dz1 = p.z2 - p.z1; int dz2 = z - p.z2; int t1 = dz2 * dx1; int t2 = dz1 * dx2; /* colinear! */ assert(t1 != t2); if (t1 > t2) { return CCW; } else { return CW; } } int in_front(Object obj, Plane p) { int viewer_x, viewer_z, viewer_orient; int front, back, i; viewer_x = p.x1; viewer_z = p.z1 - 1; viewer_orient = orient(p, viewer_x, viewer_z); /* now go through all the vertices */ front = back = 0; for (i = 0; i < obj.m; i++) { if (orient(p, obj.x[i], obj.z[i]) == viewer_orient) { front++; } else { back++; } } /* check that the object is completely in front or behind a plane */ assert(!(front && back)); return front; } void split(char *working_set, int k) { char back[MAX_N], front[MAX_N]; int i; /* we split all the way down even if there is only one object left */ /* this does not affect the correctness of the result */ if (k == p) { for (i = 0; i < n; i++) { if (working_set[i]) { putchar('A' + i); } } } else { memset(back, 0, n); memset(front, 0, n); /* find out the mask for front and back wrt plane k */ for (i = 0; i < n; i++) { if (working_set[i]) { if (in_front(object[i], plane[k])) { front[i] = 1; } else { back[i] = 1; } } } /* recurse */ split(back, k+1); split(front, k+1); } } int main(void) { int i, j; char working_set[MAX_N]; /* read input */ scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &(object[i].m)); for (j = 0; j < object[i].m; j++) { scanf("%d %d", &(object[i].x[j]), &(object[i].z[j])); } } scanf("%d", &p); for (i = 0; i < p; i++) { scanf("%d %d %d %d", &(plane[i].x1), &(plane[i].z1), &(plane[i].x2), &(plane[i].z2)); } /* process */ memset(working_set, 1, n); split(working_set, 0); putchar('\n'); return 0; }