MC 区域跳字之二

这一回的问题是，倘若需要对高度加以限制，以及区域的合并。

不妨定义“区域”为一个柱状的区域，定义“域名”为若干区域的集合。

每个域名存在一个跳名与一个真名，前者是屏幕上所跳的字，后者是创建时所定下的唯一标识符。玩家可以通过真名操作域名。

区域的合并分两种：对称差，并。

前者只需要简单合在一起，所以这里重点讲后者。

考虑把边拆出来，然后将交叉的边都切开直到没有交叉的边为止，对所有边都检查一遍是否在原来的某区域内部，把这些被原来区域所包含的边删去，最后对剩下的边求欧拉回路就行了。

具体地，首先求出所有的交点，按照 x 第一关键字 z 第二关键字排序，然后枚举所有边再枚举所有交点，找到在边上的交点，直接切断即可。最后欧拉回路时，为了使点数尽可能地少，需要尽量减少转弯的方向。

不连通的怎么办呢？直接假装出现了两条重在一起的边不就连通了。毕竟这里都是用射线法判别的。

最后一步是删去没有用的点。也就是，连续的三点共线。

然而还有一个工程上的问题，用整数是不行的，因为两边的交叉点可能是非整数的坐标。用分数其实也不行，因为可以构造出使分子分母都巨大的情形。所以最后还是只能用浮点数。

不过甲方（LXW1019）坚持用树的结构来管理域名，所以还有问题：如何判定一个域名在另一个之内。

好问题，所以先解决如何判定一个区域在另一个之内，之后稍稍重复应用下就可以了。

先看高度范围，再看平面图形是否有非端点的交点，最后看看是否所有点都被包含即可。

那么就可以写出如下代码： （坑）