线段树+扫描线 HDU-3642 Get The Treasury 题目链接：[ HDU - 3642 ] 题目大意：给你n个立方体的左下角坐标和右上角坐标，求立方体相交至少相交的面积。 题解 将Z轴离散化，把面积当作二维的底和高 代码如下 #include<bits/stdc++.h> using namespace std; const int MAXN=2010; struct Node { int l,r; int lf,rf;//实际的左右端点 int c; int once,twice,more; }segTree[MAXN*3]; int y[MAXN]; int z[MAXN]; struct Line { int x; int y1,y2; int z1,z2;//这两个是枚举的时候判断使用的 int f; }line[MAXN]; bool cmp(Line a,Line b) { return a.x<b.x; } void Build(int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; segTree[i].lf=y[l]; segTree[i].rf=y[r]; segTree[i].c=0; segTree[i].once=segTree[i].twice=segTree[i].more=0; if(r==l+1)return; int mid=(l+r)>>1; Build(i<<1,l,mid); Build((i<<1)|1,mid,r); } void push_up(int i) { if(segTree[i].c>2) { segTree[i].more=segTree[i].rf-segTree[i].lf; segTree[i].once=segTree[i].twice=0; } else if(segTree[i].c==2) { if(segTree[i].l+1==segTree[i].r)//叶子结点 { segTree[i].more=0; segTree[i].twice=segTree[i].rf-segTree[i].lf; segTree[i].once=0; return; } segTree[i].more=segTree[i<<1].once+segTree[i<<1].twice+segTree[i<<1].more +segTree[(i<<1)|1].once+segTree[(i<<1)|1].twice+segTree[(i<<1)|1].more; segTree[i].twice=segTree[i].rf-segTree[i].lf-segTree[i].more; segTree[i].once=0; } else if(segTree[i].c==1) { if(segTree[i].l+1==segTree[i].r) { segTree[i].more=0; segTree[i].twice=0; segTree[i].once=segTree[i].rf-segTree[i].lf; return; } segTree[i].more=segTree[i<<1].more+segTree[i<<1].twice +segTree[(i<<1)|1].more+segTree[(i<<1)|1].twice; segTree[i].twice=segTree[i<<1].once+segTree[(i<<1)|1].once; segTree[i].once=segTree[i].rf-segTree[i].lf-segTree[i].more-segTree[i].twice; } else { if(segTree[i].l+1==segTree[i].r) { segTree[i].more=segTree[i].once=segTree[i].twice=0; return; } segTree[i].more=segTree[i<<1].more+segTree[(i<<1)|1].more; segTree[i].twice=segTree[i<<1].twice+segTree[(i<<1)|1].twice; segTree[i].once=segTree[i<<1].once+segTree[(i<<1)|1].once; } } void update(int i,Line e) { if(segTree[i].lf>=e.y1 && segTree[i].rf<=e.y2) { segTree[i].c+=e.f; push_up(i); return; } if(e.y2<=segTree[i<<1].rf) update(i<<1,e); else if(e.y1>=segTree[(i<<1)|1].lf) update((i<<1)|1,e); else { Line temp=e; temp.y2=segTree[i<<1].rf; update(i<<1,temp); temp=e; temp.y1=segTree[(i<<1)|1].lf; update((i<<1)|1,temp); } push_up(i); } Line temp[MAXN]; int main(void) { int T; int n; int x1,y1,z1,x2,y2,z2; scanf("%d",&T); int iCase=0; while(T--) { iCase++; scanf("%d",&n); int t=0; for(int i=0;i<n;i++) { scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2); line[t].x=x1; line[t].y1=y1; line[t].y2=y2; line[t].z1=z1; line[t].z2=z2; line[t].f=1; y[t]=y1; z[t++]=z1; line[t].x=x2; line[t].y1=y1; line[t].y2=y2; line[t].z1=z1; line[t].z2=z2; line[t].f=-1; y[t]=y2; z[t++]=z2; } sort(line,line+t,cmp); sort(y,y+t); int t1=unique(y,y+t)-y; Build(1,0,t1-1); sort(z,z+t); int t2=unique(z,z+t)-z; long long ans=0; long long area=0; for(int i=0;i<t2-1;i++) { int m=0; for(int j=0;j<t;j++) if(line[j].z1<=z[i]&&line[j].z2>z[i]) temp[m++]=line[j]; area=0; update(1,temp[0]); for(int j=1;j<m;j++) { area+=(long long)segTree[1].more*(temp[j].x-temp[j-1].x); update(1,temp[j]); } ans+=area*(z[i+1]-z[i]); } printf("Case %d: %I64d\n",iCase,ans); } return 0; }

线段树+扫描线 HDU-1542 Picture 题目链接：[ HDU - 1828 ] 题目大意：给你n个矩形的左下角坐标和右上角坐标，求外周长。 题解 扫描线 + 离散化板子 将横竖两次扫描简化 代码如下 #include<bits/stdc++.h> using namespace std; const int maxn = 10010; const int maxN = 80010; const int INF = 0x3f3f3f3f; inline int read(void) { int w = 1, d = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { d = d * 10 + ch - '0'; ch = getchar(); } return w * d; } struct Node { int l, r, cnt; int lc, rc; int len, num; } tree[maxN]; struct node { int x1, x2, y, flag; void init(int l, int r, int h, int f) { x1 = l, x2 = r, y = h, flag = f; } bool operator < (const node& a) { return y < a.y; } } line[maxn]; int n, x1, y11, x2, y2; void build_tree(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].cnt = 0; tree[id].len = 0; tree[id].lc = 0; tree[id].rc = 0; tree[id].num = 0; if (l == r) return; int mid = (l + r) >> 1; build_tree(id << 1, l, mid); build_tree(id << 1 | 1, mid + 1, r); } void getlen(int i) { if (tree[i].cnt) { tree[i].len = tree[i].r - tree[i].l + 1; tree[i].lc = tree[i].rc = 1; tree[i].num = 1; }else if (tree[i].l == tree[i].r) { tree[i].len = 0; tree[i].lc = tree[i].rc = 0; tree[i].num = 0; } else { tree[i].len = tree[i << 1].len + tree[i << 1 | 1].len; tree[i].lc = tree[i << 1].lc; tree[i].rc = tree[i << 1 | 1].rc; tree[i].num = tree[i << 1].num + tree[i << 1 | 1].num - (tree[i << 1].rc & tree[i << 1 | 1].lc); } } void update(int id, int l, int r, int v) { if (tree[id].l == l && tree[id].r == r) { tree[id].cnt += v; getlen(id); return; } int mid = (tree[id].l + tree[id].r) >> 1; if (r <= mid) update(id << 1, l, r, v); else if (l > mid) update(id << 1 | 1, l, r, v); else { update(id << 1, l, mid, v); update(id << 1 | 1, mid + 1, r, v); } getlen(id); } int main(void) { ios::sync_with_stdio(false); while (~scanf("%d", &n)) { int minn = INF, maxx = -INF; for (int i = 0; i < n; i++) { x1 = read(), y11 = read(), x2 = read(), y2 = read(); maxx = max(maxx, max(x1, x2)); minn = min(minn, min(x1, x2)); line[i].init(x1, x2, y11, 1); line[i + n].init(x1, x2, y2, -1); } sort(line, line + 2 * n); build_tree(1, minn, maxx - 1); long long ans = 0, last = 0; for (int i = 0; i < 2 * n; i++) { update(1, line[i].x1, line[i].x2 - 1, line[i].flag); ans += abs(tree[1].len - last); ans += (line[i + 1].y - line[i].y) * tree[1].num * 2; last = tree[1].len; } cout << ans << endl; } return 0; }

线段树+扫描线 HDU-1542 Atlantis 题目链接：[ HDU - 1542 ] 题目大意：给你n个矩形的左下角坐标和右上角坐标，求矩形相交的面积。 题解 扫描线 + 离散化板子 代码如下 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; double dif_x[500]; struct node { double x1,x2,y; int flag; void init(double l, double r, double h, int key) { x1 = l; x2 = r; y = h; flag = key; } }line[500]; bool cmp(node a, node b) { return a.y < b.y; } struct node2 { int l, r, cnt; double len; }tree[1000]; void build_tree(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].cnt = 0; tree[id].len = 0; if(l == r) return; int mid = (r + l) >> 1; build_tree(id << 1, l, mid); build_tree((id << 1) + 1, mid + 1, r); } void getlen(int id) { if(tree[id].cnt >= 1) tree[id].len = dif_x[tree[id].r+1] - dif_x[tree[id].l]; else tree[id].len = tree[id<<1].len + tree[(id<<1)|1].len; } void update(int id,int l,int r,int v) { if(tree[id].l==l && tree[id].r==r) { tree[id].cnt += v; getlen(id); return; } int mid = (tree[id].l + tree[id].r) >> 1; if(r <= mid) update(id << 1,l,r,v); else if(l > mid) update((id << 1) + 1, l, r, v); else { update(id << 1, l, mid, v); update((id << 1) + 1, mid + 1, r, v); } getlen(id); } int mySearch(double p, int l, int r) { while(l <= r) { int mid = (l + r) >> 1; if(dif_x[mid] == p) return mid; if(dif_x[mid] < p) l = mid + 1; else r = mid - 1; } } int main(void) { int n, noc = 0; while (~scanf("%d", &n)) { if (n == 0) break; noc++; double x1, y1, x2, y2; int line_num = 0; for(int i = 0; i < n; i++) { scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); line[line_num].init(x1, x2, y1, 1); dif_x[line_num++] = x1; line[line_num].init(x1, x2, y2, -1); dif_x[line_num++] = x2; } sort(line, line + line_num, cmp); sort(dif_x, dif_x + line_num); int dif_x_num = unique(dif_x, dif_x + line_num) - dif_x; build_tree(1, 0, dif_x_num - 1); double ans = 0; for(int i = 0; i < line_num - 1; i++) { int line_l = mySearch(line[i].x1, 0, dif_x_num - 1); int line_r = mySearch(line[i].x2, 0, dif_x_num-1) - 1; update(1, line_l, line_r, line[i].flag); ans += tree[1].len * (line[i+1].y - line[i].y); } printf("Test case #%d\n", noc); printf("Total explored area: %.2lf\n\n", ans); } return 0; }

线段树+扫描线 HDU-1542 覆盖的面积 题目链接：[ HDU - 1255 ] 题目大意：给你n个矩形的左下角坐标和右上角坐标，求矩形相交至少覆盖两次以上的面积。 题解 代码如下 #include<bits/stdc++.h> using namespace std; const int maxn = 2010; double dif_x[maxn]; //记录不同的x坐标 int n, t = 0; struct node { double x1, x2, y; int flag; void init(double l, double r, double h, int key) { x1 = l, x2 = r, y = h, flag = key; } bool operator < (const node& a) const { return y < a.y; } }line[maxn]; struct Node { int l, r, cnt; double len; double len2; }tree[maxn * 4]; void build_tree(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].cnt = 0; tree[id].len = 0; tree[id].len2 = 0; if (l == r) return; int mid = (r + l) >> 1; build_tree(id << 1, l, mid); build_tree(id << 1 | 1, mid + 1, r); } void getlen(int id) { if (tree[id].cnt) //如果该段被覆盖那么就直接由dif_x数组获得长度 tree[id].len = dif_x[tree[id].r + 1] - dif_x[tree[id].l]; else if (tree[id].l == tree[id].r) tree[id].len = 0; else //如果没有被覆盖，那么应该是由左右孩子的和 tree[id].len = tree[id << 1].len + tree[id << 1 | 1].len; if (tree[id].cnt >= 2) tree[id].len2 = dif_x[tree[id].r + 1] - dif_x[tree[id].l]; else if (tree[id].l == tree[id].r) tree[id].len2 = 0; else if (tree[id].cnt == 1) tree[id].len2 = tree[id << 1].len + tree[id << 1 | 1].len; else tree[id].len2 = tree[id << 1].len2 + tree[id << 1 | 1].len2; } void update(int id, int l, int r, int v) { if (tree[id].l == l && tree[id].r == r) { tree[id].cnt += v; getlen(id); return; } int mid = (tree[id].l + tree[id].r) >> 1; if (r <= mid) update(id << 1, l, r, v); else if (l > mid) update(id << 1 | 1, l, r, v); else { update(id << 1, l, mid, v); update(id << 1 | 1, mid + 1, r, v); } getlen(id); } int main(void) { ios::sync_with_stdio(false); scanf("%d", &t); while (t--) { scanf("%d", &n); int line_num = 0; //一共有多少条横线 double x1, y11, x2, y2; for (int i = 0; i < n; i++) { scanf("%lf%lf%lf%lf", &x1, &y11, &x2, &y2); line[line_num].init(x1, x2, y11, 1); dif_x[line_num++] = x1; line[line_num].init(x1, x2, y2, -1); dif_x[line_num++] = x2; } sort(line, line + line_num); sort(dif_x, dif_x + line_num); //对dif_x去重，要先排个序，这样更方便 int dif_x_num = unique(dif_x, dif_x + line_num) - dif_x; //dif_x_num表示去重后不同的x坐标的数量 build_tree(1, 0, dif_x_num - 1); double ans = 0.00; for (int i = 0; i < line_num - 1; i++) { int ll = lower_bound(dif_x, dif_x + dif_x_num, line[i].x1) - dif_x; int rr = lower_bound(dif_x, dif_x + dif_x_num, line[i].x2) - dif_x - 1; update(1, ll, rr, line[i].flag); ans += tree[1].len2 * (line[i + 1].y - line[i].y); } printf("%.2lf\n", ans + 0.000001); } return 0; }