扫描线求矩形周长并的注意事项

在做扫描线时，对矩形的横边按照\(h\)值排序，从下往上扫描。
答案统计如代码所示

Code

点击查看代码

for (int i = 1; i <= cnt; ++i) {update(1, lbd, rbd - 1, line[i].l, line[i].r - 1, line[i].val);ans += T[1].num * 2 * (line[i + 1].h - line[i].h);ans += abs(T[1].len - lst);lst = T[1].len;
}

但不同于面积并，在求周长并时要依赖上一次根节点的\(len\)值，因此对于\(h\)相同的横边有优先级限制。
举个例子，如下图

两个矩形的入边与出边的h相同且有重合，此时如果先处理\(val\)为-1的出边，再处理\(val\)为1的入边，结合上面的代码会发现中间重合的部分算了两次！
因此正确的处理顺序应该是先处理入边再处理出边 这样就能避免这样的错误啦
可以在排序的时候判断一下\(h\)是否相同，若不相同则按照\(val\)值排序，1的优先级大于-1

Code

点击查看代码

struct ScanLine {int l, r, h, val;ScanLine() {}ScanLine(int a, int b, int c, int d) : l(a), r(b), h(c), val(d) {}inline bool operator < (const ScanLine &rhs) const {return h < rhs.h || h == rhs.h && val > rhs.val;}
} line[M];