#include #define MAX_N 50 typedef struct { int r, c, w, h; } Rect; Rect rect[MAX_N]; int n; typedef struct { int r, c; } Point; typedef struct { Point a, b; } Line; int inside(int i, int r, int c) { return (rect[i].r <= r && r < rect[i].r+rect[i].h && rect[i].c <= c && c < rect[i].c+rect[i].w); } /* only have to worry about clean intersections. Other cases are already */ /* covered by vertex in other rectangle test. */ int line_int(Line l1, Line l2) { int orient1, orient2; orient1 = (l1.a.r == l1.b.r); orient2 = (l2.a.r == l2.b.r); if (orient1 == orient2) { return 0; } if (orient1) { return (l2.a.r <= l1.a.r && l1.a.r <= l2.b.r && l1.a.c <= l2.a.c && l2.a.c <= l1.b.c); } else { return line_int(l2, l1); } } int box_int(int i1, int i2) { Point p1[4], p2[4], t; Line l1[4], l2[4]; int i, j; p1[0].r = p1[1].r = rect[i1].r; p1[0].c = p1[3].c = rect[i1].c; p1[3].r = p1[2].r = rect[i1].r + rect[i1].h - 1; p1[1].c = p1[2].c = rect[i1].c + rect[i1].w - 1; p2[0].r = p2[1].r = rect[i2].r; p2[0].c = p2[3].c = rect[i2].c; p2[3].r = p2[2].r = rect[i2].r + rect[i2].h - 1; p2[1].c = p2[2].c = rect[i2].c + rect[i2].w - 1; for (i = 0; i < 4; i++) { l1[i].a = p1[i]; l1[i].b = p1[(i+1)%4]; if (l1[i].a.r > l1[i].b.r || l1[i].a.c > l1[i].b.c) { t = l1[i].a; l1[i].a = l1[i].b; l1[i].b = t; } l2[i].a = p2[i]; l2[i].b = p2[(i+1)%4]; if (l2[i].a.r > l2[i].b.r || l2[i].a.c > l2[i].b.c) { t = l2[i].a; l2[i].a = l2[i].b; l2[i].b = t; } } for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { if (line_int(l1[i], l2[j])) { return 1; } } } return 0; } int intersect(int i, int j) { return (inside(i, rect[j].r, rect[j].c) || inside(i, rect[j].r+rect[j].h-1, rect[j].c) || inside(i, rect[j].r, rect[j].c+rect[j].w-1) || inside(i, rect[j].r+rect[j].h-1, rect[j].c+rect[j].w-1) || inside(j, rect[i].r, rect[i].c) || inside(j, rect[i].r+rect[i].h-1, rect[i].c) || inside(j, rect[i].r, rect[i].c+rect[i].w-1) || inside(j, rect[i].r+rect[i].h-1, rect[i].c+rect[i].w-1) || box_int(i, j)); } int main(void) { int i, j, c1, c2; while (scanf("%d", &n) && n) { for (i = 0; i < n; i++) { scanf("%d %d %d %d", &(rect[i].r), &(rect[i].c), &(rect[i].w), &(rect[i].h)); } c1 = 0; for (i = 0; i < n; i++) { c2 = 0; for (j = 0; j < n && !c2; j++) { if (i != j && intersect(i, j)) { c2 = 1; } } if (c2) { c1++; } } printf("%d\n", c1); } return 0; }