Snake Problem

题目

在一个平面上,有n+m条蛇,其中n条蛇沿水平方向(y轴方向)移动,m条蛇沿竖直方向(x轴方向)移动。

现给出这些蛇头和尾所在的坐标点,求出这n+m条蛇在此时共有多少个交点。在同一个方向移动的蛇不会有交点。

如图所示,n = 5, m = 4,这些蛇一共有5个交点。

Alt text

分析

对于此题,最简单直接的方法就是枚举蛇两两之间的关系,这种算法的时间复杂度为O(n^2)。

当然,我们不能满足于这种暴力的解法。那么,有没有更优美的方法呢?

Alt text

对于这一条在y轴方向上的(红)蛇来说,它与x轴方向上的(黑)蛇共有三个交点。那么,也就意味着,问题的关键在于,我们如何快速确定某一条红蛇(或黑蛇)与其它蛇一共有多少个交点。

我们可以做出如下假设,我们知道当x = k时,所有在平面上的蛇的位置。根据这个假设,我们可以使用区间求和的算法来确定竖直位置上的蛇会有多少个焦点。

假设我们从x = 0到x …

more ...