矩形的面积并

const int N = 100; //矩形的最大个数typedef double typev;struct seg{int l, r;int c;    //覆盖数typev m;  //覆盖长度}segs[N<<3];struct li{typev x, ly, hy; //ly为小的，hy为大的void set(typev x, typev ly, typev hy){this->x = x, this->ly = ly, this->hy = hy;}bool is_l;   //标记是否是左边的线段}lis[N*2];//左下角是(x1,y1)，右上角是(x2,y2), x1<x2,y1<y2的矩形struct rect{typev x1, x2, y1, y2;void read(){scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);}}rs[N<<1];typev y[N<<1];int n, cnt;bool cmp(li l1, li l2){return l1.x < l2.x;}void build(int id, int l, int r){segs[id].l = l, segs[id].r = r, segs[id].m = segs[id].c = 0;if(l < r - 1){int mid = (l+r)>>1;build(2*id+1, l, mid);build(2*id+2, mid, r);}}int binary(int l, int r, typev k){int mid;while(l <= r){mid = (l+r)>>1;if(y[mid] >= k) r = mid-1;else l = mid+1;}return r+1;}void renew(int id){if(segs[id].c > 0) segs[id].m = y[segs[id].r] - y[segs[id].l];else if(segs[id].l == segs[id].r - 1) segs[id].m = 0;else{segs[id].m = segs[2*id+1].m + segs[2*id+2].m;}}// 可以把insert和del合为一个函数void modify(int id, int l, int r, int k){if(segs[id].l >= l && segs[id].r <= r){segs[id].c += k;renew(id);}else if(segs[id].l < segs[id].r - 1){int mid = (segs[id].l + segs[id].r)>>1;if(l < mid) modify(2*id+1, l, r, k);if(r > mid) modify(2*id+2, l, r, k);renew(id);}}//n个矩形的面积并typev unionArea(rect* rs, int n){int i;typev x1, y1, x2, y2, py1, py2, area;for(i = 0; i < n; i++){x1 = rs[i].x1; y1 = rs[i].y1;x2 = rs[i].x2; y2 = rs[i].y2;lis[2*i].set(x1, y1, y2);lis[2*i].is_l = true;lis[2*i+1].set(x2, y1, y2);y[2*i] = y1;y[2*i+1] = y2;lis[2*i+1].is_l = false;}n <<= 1;sort(y, y + n);sort(lis, lis+n, cmp);cnt = unique(y, y + n) - y;build(0, 0, cnt-1);area = 0;for(i = 0; i < n-1; i++){py1 = binary(0, cnt-1, lis[i].ly);py2 = binary(0, cnt-1, lis[i].hy);if(lis[i].is_l) modify(0, py1, py2, 1);else modify(0, py1, py2, -1);area += (lis[i+1].x - lis[i].x) * (segs[0].m);}return area;}