算法问题实战策略——15.10　解题：是呆子？不是呆子？

变换成几何问题 此题看似完全不是几何题，其实，巧妙变换即可。实行变换的第一个线索是，每人有两项调查资料，因此，把每人的鞋子尺码和每分钟的打字速度分别视为x、y坐标，就能把输入的数据表示成N个点。图15-13(a)是第一个示例的图形，图中的○表示呆子，×表示不是呆子的人。每个人的信息已表示成图表形式，接下来把区分呆子和不是呆子的人的公式也表示成图表形式。对于是呆子的人，如下公式将成立。 A•x+B•y≥T 图15-13　把“是呆子？不是呆子？”问题的输入值表示成二维平面上的点 将此公式表示成图表后，将会是半平面。也就是说，以一条直线为基准，一侧是呆子，另一侧不是呆子。因此，图中能够找出一条分割呆子和不是呆子的直线，上面的公式必定存在。图15-13(a)表示区分这两种人的直线，而图15-13(b)中不存在这种直线，所以这种情况的假设理论不成立。 凸包建模 现在，此题已变换为“在平面上给出两种类型的点时，判断有无直线能将这两类点相互分隔”的问题。虽然有多种方法可以解决此题，但此题意在利用凸包（convex hull）解决。所谓凸包就是，能够包含二维平面上所有点的面积最小的多边形。图15-14(b)表示图15-14(a)中所有点的凸包。因为面积最小，所以多边形的所有顶点都由原来给出的点组成。找出凸包的问题是计算几何的基础问题之一，所以常常能够在程序设计竞赛中见到其身影。 能够找出凸包，此题就会变得更简单。假设对两种类型的点分别求出了凸包。如果存在一条直线能够把这两种点进行分隔，那么这条直线也能够分隔这两个凸包。只要两个多边形没有连接或重叠在一起，分隔两个多边形的直线就必定存在。相反，如果两个多边形相互重叠，就不会存在这样的直线。因此，只要求出凸包，就能通过判断两个多边形是否重叠或相互连接以解决此问题。 图15-14　凸包示例 找出凸包 找出凸包问题是常见几何问题，为了解决此问题，现已开发出很多具有不同时间复杂度的算法。本节将介绍其中最直观、最容易理解的卷包裹算法（Gift wrapping algorithm）。卷包裹算法首先找出能被凸包包含的1个点，然后向该点连接假想的“包装纸”——射线，按顺时针方向旋转此射线以包裹所有点。图15-15是这种算法的执行过程，虚线表示“包装纸”，实线表示已被包裹的部分。 虽然卷包裹算法的工作原理非常直观，不过，要实现这种算法并不容易。因为，很难通过旋转假想的射线以找出遇到的第一个点。因此，实现卷包裹算法的过程中并不直接使用包装纸的概念，而是在给出包装纸最后遇到的点p时检查所有点。此时，从p到各个点的向量中，最左边的向量对应的点就是包装纸下一个将遇到的点。因为p点在凸包上，所以最左边的向量只能存在1个。下面比较图15-16(a)和(b)。(a)中，从凸包上的点画出的到其他点的向量都在180度范围内。因此，可以把最左边的向量对应的点定义为下一个要遇到的点。反之，如图(b)所示，从凸包内部的点开始画出到其他点的向量时，将无法判断哪个向量在最左侧。卷包裹算法将把找出的点包含到凸包的边上，然后继续执行该过程，直到返回起点。 图15-15　卷包裹算法的执行过程 图15-16　在卷包裹算法中找出下一个被凸包的边包含的点 代码15-13是实现卷包裹算法的示例代码，查看时请留意以下几点。  vector2类中已经实现了比较运算，所以能够非常容易地找出最左边的点。此处利用了STL的min_element函数。  while语句内部通过ccw()函数求出了从凸包边上的点ph到向量处在最左边位置的点。此处要注意，叉积等于0。这就意味着next、points[i]、ph都在同一直线。此时应当找出距ph最远的点，并将其作为下一个顶点。因为，处在此点与ph之间的点没有必要被包含在凸多边形的边上。为此计算了各点与ph之间的距离差dist。这种比较在next或points[i]等于ph时也能用到。 代码15-13　找出凸包的卷包裹算法 typedef vector<vector2> polygon; // 找出能够包含points中所有点的最小凸多边形。 polygon giftWrap(const vector<vector2>& points) { int n = points.size(); polygon hull; // 找出最左下角的点。并将此点包含到凸包的边上。 vector2 pivot = *min_element(points.begin(), points.end()); hull.push_back(pivot); while(true) { // 从ph起始的向量中，找出最左边位置的点next。 // 有多个平行点时，选择最远的。 vector2 ph = hull.back(), next = points[0]; for(int i = 1; i < n; ++i) { double cross = ccw(ph, next, points[i]); double dist = (next - ph).norm() - (points[i] - ph).norm(); if(cross > 0 || (cross == 0 && dist < 0)) next = points[i]; } // 返回起点则终止运算。 if(next == pivot) break; // 将next包含到凸包的边上。 hull.push_back(next); } return hull; } 凸包中每增加1个顶点，卷包裹算法的while语句就会循环执行1次。每次循环的时间复杂度是O(N)，所以凸包的顶点个数为H时，整个算法的时间复杂度为O(NH)。那么，在最坏的情况下，也就是所有点都成为凸包顶点时，卷包裹算法的时间复杂度为O(N2)。此题的N≤5000，所以这种程度的时间复杂度不会构成大问题。 需要对更多点求出凸包时，可使用葛立恒扫描（Graham Scan）算法。此算法能够在O(NlgN)时间内完成运算。 多边形相交判定 利用giftWrap()函数求出两种类型点的凸包后，接下来要判定两个凸多边形是否相互接触。对于此问题，可利用已编写的几何代码简单求解。代码15-14是以最简单的方式判定多边形相交的polygonIntersects()函数。代码中，首先把一个多边形完全包含另个一个多边形的情况处理为异常。第一次写此代码时，很容忽略这种异常。排除异常后，为了使两个多边形重叠，必须存在两条重叠或相互连接的边。polygonIntersects()函数将在for语句内部中调用segmentIntersects()函数，以检索每对边。 代码15-14　确认两个凸多边形是否相交的polygonIntersects()函数 // 返回两个多边形是否相连或重叠。 // 即使只在1个点上重叠，也返回true。 bool polygonIntersects(const polygon& p, const polygon& q) { int n = p.size(), m = q.size(); // 首先确认一个多边形是否被另一个多边形完全包含。 if(isInside(p[0], q) || isInside(q[0], p)) return true; // 除此之外，如果两个多边形相互重叠，那么肯定存在两条相互连接的边。 for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) if(segmentIntersects(p[i], p[(i+1)%n], q[j], q[(j+1)%m])) return true; return false; } polygonIntersects()函数的时间复杂度受嵌套两层的for语句支配，因此，对于两个多边形包含的点的个数A、B，将具有O(AB)的时间复杂度。不过，求凸包时的时间复杂度已经达到O(N2)，所以整个算法的时间复杂度将不会发生变化。 线性可分 这种对二维空间上的不同类型点判断有无可分直线的问题，就是线性可分（linear separability）问题。最早的机器学习算法之一——感知器（perceptron）就通过找出对给定数据的分隔直线进行运算。不过，随着此算法不能解决线性不可分问题 的事实得到证明，其进入低潮期。 关于可视化 将要解决的问题转换成可视化形态求解的方法可应用于许多问题。有些题转换成可视化形态后，可以直接找出解决方法。而有些题虽然不能直接找出解决方法，但至少能够加深对问题的了解，因为人类大脑更容易识别平面图形而非数值。