可能是没怎么搞计算几何的知识，至今对扫描线算法没有很清晰的认识，记得当初ZY大神是这样定义的：
每一个事件有一个开始时间和结束时间，将所有时间点排序，然后依次扫描，如果是开始时间就将时间加入，否则就将事件删除。则可以在任意时刻处理当前发生的事件。
扫描线在计算几何中使用相对多一些，我只是为了刷通线段树的列表粗略了了解了一下，只可就事论事，无法统筹全局。“矩形面积并”是扫描线与线段树结合的一个经典应用，同时也是区间离散化的一个经典例子。
矩形面积并：平面上有N个矩形，各边均平行于坐标轴，求它们覆盖的总面积（重复覆盖的只计一次）。
解法：将矩形的竖边按照x坐标排序，每个矩形看做一个事件，矩形的左竖边看做事件的开始右竖边看做事件的结束，这样可以计算任意两条临边之间属于矩形并的面积（当前覆盖的纵坐标*横坐标差），过个图应该就可以理解了。。。
接下来就是区间离散化和维护统计量的过程了，离散化后横坐标有m个，如果建立m个节点那么线段树节点的长度无法计算（最简单的就是叶子节点，长度为0显然不对），因此线段树中建立m-1个叶子节点，第i个叶子节点代表i~i+1之间的距离（做到这里才知道当初对Poster那题的理解是一知半解的，不是半开半闭的问题而是节点保存什么信息的问题）。矩形面积并的线段树比较奇怪，虽然更新的是区间的值但是却不需要pushdown操作。而且更新自区间后也立即pushup（），线段树变化多端一定要灵活啊。。。
poj1151 Atlantis 需离散化的浮点矩形面积比
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;
public class Atlantis1151 {
class SegTree {
class node {
int left, right, key;
double sum;
void init(int l, int r) {
left = l;
right = r;
sum = 0;
key = 0;
}
int mid() {
return (left + right) >> 1;
}
double length() {
return hash[right + 1] - hash[left];
}
}
node tree[];
SegTree(int maxn) {
maxn = maxn * 3;
tree = new node[maxn];
for (int i = 1; i < maxn; i++)
tree[i] = new node();
}
void init(int l, int r, int idx) {
tree[idx].init(l, r);
if (l == r)
return;
int mid = tree[idx].mid();
init(l, mid, idx << 1);
init(mid + 1, r, (idx << 1) | 1);
}
void update(int left, int right, int idx, int v) {
if (tree[idx].left >= left && tree[idx].right <= right) {
tree[idx].key += v;
pushup(idx);
return;
}
int mid = tree[idx].mid();
if (left <= mid)
update(left, right, idx << 1, v);
if (right > mid)
update(left, right, (idx << 1) | 1, v);
pushup(idx);
}
void pushup(int idx) {
if (tree[idx].key > 0)
tree[idx].sum = tree[idx].length();
else {
if (tree[idx].left == tree[idx].right)
tree[idx].sum = 0;
else
tree[idx].sum = tree[idx << 1].sum
+ tree[(idx << 1) | 1].sum;
}
}
}
Scanner scan = new Scanner(System.in);
class edge implements Comparable<edge> {
int s, t, v;
double x;
public int compareTo(edge oth) {
if (x < oth.x)
return -1;
if(x==oth.x&&v>oth.v)
return -1;
//在求矩形周长并时发现的错误，貌似面积并沒问题，也许是数据太弱的缘故，先写上，稍后研究
return 1;
}
}
class zone implements Comparable<zone> {
int id;
double h;
public int compareTo(zone o) {
if (h < o.h)
return -1;
return 1;
}
}
SegTree st = new SegTree(310);
edge[] ed = new edge[310];
zone[] zn = new zone[310];
int n, cnt;
double hash[] = new double[310];
void hash() {
Arrays.sort(zn, 1, n * 2 + 1);
cnt = 1;
for (int i = 1; i <= 2 * n; i++) {
if (i>1&&zn[i].h != zn[i - 1].h)
cnt++;
hash[cnt] = zn[i].h;
int temp = zn[i].id;
if (temp > 0)
ed[temp].s = ed[temp + 1].s = cnt;
else
ed[-temp].t = ed[-temp + 1].t = cnt;
}
}
void init() {
for (int i = 0; i <= 300; i += 2) {
ed[i] = new edge();
ed[i + 1] = new edge();
zn[i] = new zone();
zn[i + 1] = new zone();
}
}
void run() {
int cas = 0;
DecimalFormat df = new DecimalFormat("0.00");
init();
while (true) {
cas++;
n = scan.nextInt();
if (n == 0)
break;
System.out.println("Test case #" + cas);
for (int i = 1; i <= n * 2; i += 2) {
ed[i].x = scan.nextDouble();
ed[i].v = 1;
zn[i].id = i;
zn[i].h = scan.nextDouble();
ed[i + 1].x = scan.nextDouble();
ed[i + 1].v = -1;
zn[i + 1].id = -i;
zn[i + 1].h = scan.nextDouble();
}
hash();
Arrays.sort(ed, 1, n * 2 + 1);
st.init(1, cnt - 1, 1);
st.update(ed[1].s, ed[1].t - 1, 1, 1);
double ans = 0;
for (int i = 2; i <= n * 2; i++) {
ans += st.tree[1].sum * (ed[i].x - ed[i - 1].x);
st.update(ed[i].s, ed[i].t - 1, 1, ed[i].v);
}
System.out.println("Total explored area: " + df.format(ans));
System.out.println();
}
}
public static void main(String[] args) {
new Atlantis1151().run();
}
}
Ps：很多大神离散化喜欢用二分做，具体的编码复杂度和事件复杂度有待进一步对比，但还是感觉写自己的方法比较顺手，因此暂时不改了。
矩形周长并：比面积并稍微复杂一些，横边和竖边要分别统计。贴个pushup（）和统计代码，然后画张图应该就可以理解了（注意两条竖边重合的情况，poj1177discuss里有这种数据）
void pushup(int idx) {
if (tree[idx].cnt > 0) {
tree[idx].sum = tree[idx].length();//区间覆盖长度
tree[idx].lp = tree[idx].rp = 1;//左右端点是否被覆盖
tree[idx].num = 1;//区间内共有几个分散区间
} else {
if (tree[idx].left == tree[idx].right) {
tree[idx].num = tree[idx].sum = 0;
tree[idx].lp = tree[idx].rp = 0;
} else {
int l = idx << 1;
int r = l + 1;
tree[idx].lp = tree[l].lp;
tree[idx].rp = tree[r].rp;
tree[idx].sum = tree[l].sum + tree[r].sum;
tree[idx].num = tree[l].num + tree[r].num
- (tree[l].rp & tree[r].lp);
}
}
}
for (int i = 1; i <= n * 2; i++) {
if (i > 1)
ans += st.tree[1].num* (ed[i].x - ed[i - 1].x) * 2;//横边
st.update(ed[i].s, ed[i].t - 1, 1, ed[i].v);
ans += Math.abs(st.tree[1].sum - last);//竖边
last = st.tree[1].sum;
}