#include #include #define MAXN 1000 struct Edge { double main, left, right; int open;}; struct Node { double covered; int tables; double left, right; int leaf;}; int edgecmp(const void * a, const void * b) { struct Edge * p = a, * q = b; if (p->main != q->main) return p->main - q->main; if (p->open != q->open) return p->open ? -1 : 1; return 0; } int n, s; double perim; struct Edge ve[2 * MAXN], he[2 * MAXN]; struct Node tree[8 * MAXN + 1]; void buildTree(struct Edge * f, int p, int l, int r) { tree[p].covered = 0; tree[p].tables = 0; tree[p].left = f[l].main; tree[p].right = f[r].main; tree[p].leaf = 1; if (r - l == 1) return; int m = (l + r) / 2; tree[p].leaf = 0; buildTree(f, 2*p, l, m); buildTree(f, 2*p+1, m, r); } double update(int p, struct Edge * edge) { if (edge->right <= tree[p].left || edge->left >= tree[p].right) return 0; double sum = 0; if (edge->left <= tree[p].left && edge->right >= tree[p].right) { if (edge->open && !tree[p].tables++) sum = tree[p].right - tree[p].left - tree[p].covered; else if (!edge->open && !--tree[p].tables) { sum = tree[p].right - tree[p].left; if (!tree[p].leaf) sum -= tree[2*p].covered + tree[2*p+1].covered; } } else { sum = update(2*p, edge) + update(2*p+1, edge); if (tree[p].tables) sum = 0; } if (tree[p].tables) tree[p].covered = tree[p].right - tree[p].left; else tree[p].covered = tree[p].leaf ? 0 : tree[2*p].covered + tree[2*p+1].covered; return sum; } void makeEdge(struct Edge * edge, double main, double left, double right, int open) { edge->main = main; edge->open = open; edge->left = left; edge->right = right; } int main(void) { scanf("%d", &n); s = 2 * n; int i; for (i = 0; i < n; i++) { double x, y, w, h; scanf("%lf%lf%lf%lf", &x, &y, &w, &h); makeEdge(he + 2 * i , y - h, x, x + w, 1); makeEdge(he + 2 * i + 1, y, x, x + w, 0); makeEdge(ve + 2 * i , x, y - h, y, 1); makeEdge(ve + 2 * i + 1, x + w, y - h, y, 0); } qsort(he, s, sizeof(struct Edge), &edgecmp); qsort(ve, s, sizeof(struct Edge), &edgecmp); buildTree(ve, 1, 0, s - 1); for (i = 0; i < s; i++) perim += update(1, &he[i]); buildTree(he, 1, 0, s - 1); for (i = 0; i < s; i++) perim += update(1, &ve[i]); printf("%2.2f\n", perim); return 0; }