国家集训队2005论文集
为它较容易实现，减少或避免了编程错误，反而能得到意想不到的好结果。
4.2 缺点
非正确性：这是不言而喻的，非完美算法，值得利用的就是它的非正确性。但非正确性使得算法不仅依赖算法的好坏、代码的好坏，还依赖于数据。如果数据较弱，非完美算法可能得到较高的分数，如果数据较强，其结果不一定很理想。
【总结】
本文主要介绍了非完美算法的几种重要方法。从上面的算法可以看到，并不是正确的算法就一定好过不完全正确的算法，因为非完美算法的不完全性，反而使非完美算法在很多方面比正确算法表现得更好。因此，合理的使用非完美算法能使我们得到令人满意结果。
【感谢】
衷心感谢向期中老师在我写这篇论文时对我的指导和帮助。
衷心感谢刘汝佳教练对我的指导和启发。 衷心感谢王俊、任恺同学对我的支持和帮助。
衷心感谢肖湘宁、周戈林同学在临近期末考试时还能为我看论文，并向我提很多宝贵的意见，特别感谢周戈林同学提供NOIP2003《传染病控制》的解题报告。
【参考文献】
《论随机化算法的原理与设计》——周咏基,1999
《The CRC Concise Encyclopedia of Mathematics》——Eric W. Weisstein,CRC Press
《计算几何——算法分析与设计》——周培德,清华大学出版社,广西科学技术出版社
《算法艺术与信息学竞赛》——刘汝佳、黄亮，清华大学出版社
《IOI'04: Solution of Polygon》——Ioannis Emiris and Elias Tsigaridas,2004
【附录】
国家集训队2005论文集
传染病控制原题(NOIP2003)
【问题背景】
近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国 大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完 全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是， 蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫 生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究 消楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。
【问题描述】
研究表明，这种传染病的传播具有两种很特殊的性质；
第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不 得病，或者是XY之间的传播途径被切断，则X就不会得病。
第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一 代患者，而不会再传播给下一代。
这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群 的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同 时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而 没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有 传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止 传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。 你的程序要针对给定的树，找出合适的切断顺序。
【输入格式】
输入格式的第一行是两个整数n（1≤n≤300）和p。接下来p行，每一行有两个整数i 和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点 1是已经被感染的患者。
【输出格式】
只有一行，输出总共被感染的人数。
国家集训队2005论文集
【输入样例】 7 6 1 2 1 3 2 4 2 5 3 6 3 7
【输出样例】 3
Polygon中文原题
【问题描述】
凸多边形的定义如下：多边形内任意两点X和 Y 的连线上的所有点都在多边形内部。在本题中的所有多边形都是拥有至少两个顶点的凸多边形并且所有顶点互不相同，且具有整数坐标。多边形的任意三个顶点不共线。在下文中的“多边形” 一词都是指这样的多边形。
给定两个多边形A 和 B， A 和 B 的Minkowski 和 包含所有形如(x1+x2, y1+y2) 的点，其中 (x1, y1) 是 A 中的点，(x2, y2) 是 B 中的点。多边形的Minkowski 和也是一个多边形。下图是一个例子：两个三角形和它们的 Minkowski 和。
我们考虑Minkowski 和 的一种逆运算。给定一个多边形P, 我们寻找两个多边形A 和 B ，满足:
- P 是A 和 B 的Minkowski 和,
- A 有2 到 4 个不同的顶点，例如，它是一条线段（2个顶点）, 一个三角形（3个
顶点），或一个四边形（4个顶点）， - A 必须包含尽可能多的顶点，例如：
A 如果可能的话，必须是一个四边形，
如果 A 不可能是一个四边形而有可能是一个三角形，则它必须是一个三角
形，
否则它是一条线段。
很显然， A 和 B 都不能等于 P ，因为如果其中一个等于P， 则另一个只能是一个点，而点不是一个合法的多边形。
国家集训队2005论文集
给定多个输入文件，每个输入文件描述一个多边形P。 对于每一个输入文件，你必须找出满足上述条件的A 和 B， 并且创建一个文件来描述A 和 B 。 对于所有给定的输入文件， A 和 B 一定存在。如果存在多组解，只需要输出其中的任意一组。不要提交源程序，只需要提交输出文件。
【输入格式】
共有十组输入文件从 polygon1.in 到 polygon10.in, 在polygon 后的数字是输入文件序号。每个输入文件的构成如下：第一行包含一个整数N： 多边形 P的顶点个数。 接下来的N 行以逆时针方向描述了N 个顶点的坐标，每个顶点一行。第I+1 (I = 1, 2, ..., N) 行包含两个整数XI 和 YI， 以一个空格隔开，表示第I 个顶点。所有坐标为非负整数。
【输出格式】
针对给定的输入文件，你需要给出相应的10个输出文件用以描述相应的A 和 B。输出文件的第一行应包含：
#FILE polygon I
这里整数I 表示相应的输入文件序号。
输出文件的格式与输入文件类似。第二行包含一个整数 NA：A中的顶点数 (2≤NA≤4)。 接下来的 NA 行以逆时针方向描述A 的NA个顶点，每个顶点一行。第 I+2 ( I = 1, 2, ..., NA) 行包含两个整数 X 和 Y, 以一个空格隔开：表示A的第I个顶点。