④
具体的最小强伪质数列表请见附录。
国家集训队2005论文集
例：Polygon⑤ 题目大意
在此题中，所有的多边形均指凸多边形。
给定两个多边形A和B，A和B的Minkowski和是指包含所有形如(x1+x2, y1+y2) 的点的多边形，其中(x1,y1) 是A中的点，(x2,y2)是B中的点。
我们考虑Minkowski和的一种逆运算。给定一个多边形P, 我们寻找两个多边形A和B，满足：
- P是A和B的Minkowski和；
- A有2到4个不同的顶点(线段、三角形或四边形)； - A必须包含尽可能多的顶点。
说明：此题附官方解答，其复杂度为O(N2m2)，其中N为多边形P的顶点数，m为P的边上的整点个数的最大值 分析
由于本题中，位置并不是很难处理，所以此题将不考虑多边形的位置问题，只考虑其形状和大小。
根据定义可以知道，对两个多边形A、B求Minkowski和，就是将它们的所有的边看作有顺序的向量，对所有向量按其级角排序，然后将所有的向量顺次连接，最后将共线同向的向量合并的过程。
①
③
⑦⑥
多边形A
多边形B
相加前
⑤
②
多边形P 合并共线同向向量
将所有向量按极角按序，首尾相连
题目来源：IOI2004，中文原题请见附录，英文原题在附件中《polygon-1.2》。
国家集训队2005论文集
由上面加法的过程不难想到，原来的多边形A、B的每条边在P中仍存在一条边与原边共线同向且模不小于原边，因此：
将一个多边形P拆成边数为K的多边形A与不定边数的多边形B相加的形式，就是要从P中找出K条边，从每边取出一段(或整条边)，使这K段正好能围成一个多边形，这个多边形就是A，剩下的按照向量首尾相连可得到B。
如：从上图的多边形P中取一个边数为2的多边形：
②
⑥
①
⑥
② ⑤1
③
边②和边⑤的一部分正好可以围成二边形
④
取出这两部分
⑤2 ⑤1
④
两部分和剩下的部分分别围成一个多边形
⑤2
从P中取出一个三角形、四边形，也是同样的方法。 这个算法看起来很简单，但实现起来并没有想象中那么轻松。 找一个二边形，只要找到一对共线向量即可。
找一个三角形，可以枚举三条边，然后判断，其复杂度是O(N3m3)。在提交答案类题看来，已经很不错了。
找一个四边形，如果枚举四条边，然后判断，其复杂度是O(N4m4)，因其中的m是未知的，所以不敢轻易使用。这时可以枚举三条边，另一条边通过对边的二分查找得到。由于第四条边可能是多边形P中某条边的一段，而P中一共可能有N*m段，因m未知，使得空间分配也不好处理；同时，由于存储时不仅要存储每段所对应的原来的边的序号，还要存储每段是占原来的几分之几 此时遇到的问题可能还远不只这些，这时，就很难保证程序不出错。
这种，不妨做一个大胆的假设：假设第四条边是P中的一条完整的边。这样，只要存储P条边即可，且这P条边都是原来多边形中的完整的边，所以编程中要考虑的问题就少多了，同时出错的可能性也小多了。
这样做，对于官方的数据，有9个测试点可以出解，所出的解全部是最优解。
国家集训队2005论文集
另一个测试点可以用手做。
部分忽略法的实际应用
下面看一下判断一个点P是否在一个简单多边形内的算法：
假设已经判断了P在多边形边上这种特殊情况，剩下的只有点在多边形内和外的问题。
传统的判断算法是：以P为端点作一条射线，然后根据射线与多边形的交点个数是奇数个还是偶数个来判断其是否在多边形内。
但是，在计算交点个数的时候，有一种特殊情况：所作的射线经过多边形的某个顶点(有可能更特殊的与多边形的一条边重合)。如下图：
(a) (b)
在(a)中，处理的结果应为射线与多边形有奇数个交点，而(b)中，处理的结果应为射线与多边形有偶数个交点，如果不加特殊处理，则两种情况所得到的结果是相同的。
如果采用部分忽略法似乎会出现错误。但是，如果取的射线是一条很“一般”的射线：如在平面内随机取一个异于P的点Q，且保证Q的坐标有若干位小数，从P作一条射线，使射线经过Q，则，可以说，要出错的概率是非常小的。如果多取几个点，分别对这几个点进行判断，然后取这些结果中出现得最多的结果，则要出错就更不可能了。
小结
通过上面的例题可以看出，能过忽略部分复杂情况，能使算法的思考复杂性和编程复杂性降低。仅管它可能造成算法在一定程度上的错误，但这种错误通常是很小的。所以，有时采用部分忽略法仍是非常好的选择。
国家集训队2005论文集
三、非完美算法的依据——RP类问题与Monte-Carlo算法
前面所讲的一些方法，似乎都是靠的“运气”成分。但是，这些算法有它的依据：
如果一个问题存在一个随机算法，使得它有50%以上的概率得到期望的结果，那么这个问题属于RP类问题。该算法称为Monte-Carlo算法。
如果一个问题是RP类问题，可以通过多次运行它的一个Monte-Carlo算法而得到“几乎每次都是正确”的算法。
由于RP类问题与Monte-Carlo算法不是本文研究的重点，这里不再多做介绍，有兴趣的读者可以参阅相关的资料。
四、非完美算法的共性
非完美算法有很多种，但是，它们并不是完全不同的，它们之间存在一个共同的性质，那就是不完全性。上面的非完美算法都是由于其不完全性而使得它们具有一些完全正确的算法所不能具备的优势，同时，其不完全性也导致了算法不是完全正确的。
五、非完美算法的优点与缺点
4.1 优点
从上面的分析和举例，相信读者对非完美算法的优点已经有所了解了，现整理如下：
①时空消耗低：这是非完美算法的一个最突出的优点，也是大多数情况下使用它的原因。
②编程复杂度低：因为非完美算法会可能绕过纷繁的处理或会忽略掉非常难处理的一些情况，其编程复杂度可以得到一定的降低。在比赛中，低的编程复杂度往往比低的算法时间复杂更容易得到令人满意的结果。
③思维复杂度低：同样也是因为非完美算法可能忽略掉非常难处理的一些情况。
④能减少编程错误：通过前面几点，这点也就显然了。也许，一个非常优秀的算法，因为它的一点点小错误，就导致其前功尽弃，而一个非完美的算法，因