计算几何系列

       本系列文章力求以简洁易懂的文字介绍计算几何中的基本概念，使读者快速入门，故不追求难度和深度，仅起到抛砖引玉的作用。     

       在我们的计算几何中，乃至基本的几何学中我们都需要解决一类问题，那就是几何图形的面积交并，周长交并问题，在计算几何中我们也常常遇到这样的问题，在这里我们介绍一种神奇的用来解决这类问题的算法，叫做扫描线（scan line algorithm）算法，是2018年公布的计算机科学技术名词，主要倾向于线段树+离散化这类思想，然后扫描求解过程有点像积分，那么我们开始讲解扫描线。

      我们先来看一个最基础的问题： 

      看到n的数据范围是：

      看到这个以后，我们是要去打ACM的话，肯定只考虑100%的数据，因此O(n^2)的算法直接被我们抛弃，这样子主要考虑O(n)或者O(nlogn)的算法，那么就是我们今天的算法:扫描线算法，时间复杂度是O(nlogn)的，接下来讲一下这个算法的运作过程。

  问题在于如何才能模拟扫描线从下向上扫过图形，并且快速计算出当前扫描线被截得的长度。

  现在假设，扫描线每次会在碰到横边的时候停下来，如图👇：

      简单来说，可对图形面积产生影响的元素，也就是这些横边左右端点的坐标。那么还有一个很严重的问题就是，如何加边减边的问题，就是在某个区间怎么判断这条边还在吗？这个很简单，我们只需要在一个矩形的上下两边加上不同的权值，按照扫描方向，假如方向是从下往上，那么下方的边权就是1，上方的边权就是-1，这样子就解决了边的存在问题了：       然后把所有的横边按照矩形y坐标升序排序。这样，对于每个矩形，扫描线总是会先碰到下边，然后再碰到上边。那么就能保证扫描线所截的长度永远非负了。这样操作以后，就可以和线段树扯上关系，我们只需要在输入的时候将每个矩形的横坐标剥离出来，放在x轴上进行离散化。（其实就是把所有点的横坐标存到X[]里，然后升序排个序，最后去重。）

       👆：在这个例子中，4个端点的纵投影总共把x轴切割成了5部分。取中间的3部分线段，建立一棵线段树，其每个端点维护一条线段（也就是一个区间）的信息：

      显然，只要一条线段被覆盖，那么它肯定被图形所截。所以，整个问题就转化为了一个区间查询问题，即：每次将当前扫描线扫到的边对应的信息按照之前赋上的权值更新，然后再查询线段树根节点的信息，最后得到当前扫描线扫过的面积。这就可以用线段树来实现了（线段树：顾名思义，就是树上的结点为一条条线段~），接下来我们来简单看一下模拟过程：

      那么对于这样的一个基本情况就是这么简单的模拟，我们只需要建立一棵线段树来存储这些线段就OK了，但是问题来了，我们应该存储线段的那些信息？这些线段应该怎么存？（开区间 or 闭区间 or 半开半闭）

      所以为了保证线段之间的兼容性，我们一般这么考虑：考虑把线段树每个节点x对应的区间（tree[x].l,tree[x].r）不变，改变区间和横边的映射关系，具体为：节点x对应[X[tree[x].l],X[tree[x].r + 1]这条横边，如果不这样想可能会出现线段之间的端点重合问题，实在是细腻啊~，所以我们建树这样子建（保存的信息还是一样，提取的时候搞一下操作）：

        然后我们只需要在更新线段树的时候做操作~：