计算几何系列 —— 扫描线算法

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

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

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

      看到n的数据范围是：

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

扫描线：假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果（相当于是每次算出每个单位长度上的微分，最后积起来这样的一个过程）。该过程可以用线段树进行加速。

       由于都是矩形，因此运用扫描线以后，面积的求法其实可以简化为 ∑截线段长度×扫过的高度，这也是扫描线算法最基础的应用。

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

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