国家集训队2004论文集_金恺

《国家集训队2004论文集_金恺》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2004国家集训队论文金恺极限法——解决几何最优化问题的捷径长郡中学金恺【关键字】最优值极限无穷小微调【概述】在平面几何问题中我们经常会遇到一些求极值的问题。在这些问题中，自变量和目标函数可能涉及到坐标、斜率、长度、角度、周长、面积等等一些复杂的量，而且往往自变量还有一些复杂的约束条件，因此直接用函数求极值的方法是行不通或极其复杂的。这些问题中，变量往往有无穷多种取值方案（比如说点的取值范围可能是整个平面或在某条直线上），所以无法枚举每一种取值方案来找最值，这时往往能够通过极限法证明：自1变

2、量取某些非特殊情况值时目标函数不可能是最优的——因为这时经过微调一个无穷小量能够使得目标函数的值变得更优，从而剩下有限种特殊的取值情况可能成为最优解，通过枚2举所有特殊情况就能找到目标函数的最优解了。在另一些同类问题中，本来就可以通过枚举有限个取值情况求出最优解，但是枚举的量很大，时间复杂度较高，我们也可尝试通过极限法来大大减少需要枚举的情况，从而降低时间复杂度。以上就是极限法的大致思想，它的作用简而言之就是化无限为有限，变有限为少量。正文3极限法的应用实例非常的多，比如经典的最小矩形覆盖问题，就

3、是通过极限法证明了：最小矩形的某条边必须过两个已知点，从而大大减少了需要枚举的矩形数目。然而极限法用起来的确有较大的困难，有时候证明起来非常困难，可能情况比较复杂，也可能不知道如何调整，需要用到三角函数之类的比较复杂的数学知识，因此真正掌握它需要扎实的数学功底，极强的观察力以及必要的经验是必不可少的。下面就来用极限法解决一些典型问题，从实例的分析中一步一步深入地认识极限法的用途和用法。例题一、巧克力1比如旋转一个无穷小的角度、微移一段无穷小的距离。在本文中，微量这一名词就是指无穷小量：只要改变得足

4、够小（无穷小），就能使点的相对位置、线段的相交情况等不发生改变。2极限法的本质也就是对目标函数求导，如果导数不为0并且自变量不在定义域的边界则不可能为最优值。这正是采用“极限法”来命名的原因。3平面上有n个已知点，求一个面积最小的矩形，使得所有已知点都在矩形的内部。第1页共12页IOI2004国家集训队论文金恺问题描述：糖果厂有一种凸起的N（4≤N≤50）边形巧克力，Kiddy和Carlson凑钱买了一块，想把它用一刀割成两半。两半的大小必须相等，找出用以分割巧克力的分割线的最短长度。数学模型：已

5、知N个点(Xi,Yi)1≤i≤N构成一凸包P{已知量}，求一条划分线L，使得分割线两侧的面积相等{约束条件}，并且使L的长度{目标函数}最小。问题分析：设分割线的两个端点分别为A、B，A、B可能在P的顶点上也有可能只在P的边上{不含端点}。我们分开解决这两种情况：A1、A在P的顶点上（或B在P的顶点上，此时交换SL=SRAB）：显然可以枚举P中的一个顶点作为A，由分割SLLSR线两侧面积相等这一约束条件直接确定B的位置，如图1。B2、A、B都在P的边上：枚举A、B所在的两条边，设这两条边相交于C，

6、如图2：图1AA’αα+θθθL’L图2β-θβB’BγC设∠C=γ，∠CAB=α，∠CBA=β。当α≠β时，可以证明：把分割线L稍微旋转一个无穷小量θ到L’并保持L’两边的面积相等，能够使L’的长度小于L。证明如下：不妨设α>β，旋转后L’仍与原来的两边相交（因为仅旋转了一个无穷小量），交点为A’、B’，∠CA’B’=α+θ，∠CBA=β-θ。ACBCL在三角形ABC中，有正弦定理：==sinbsinagsinA¢CB¢¢CL在三角形A’B’C中，有正弦定理：==sin()b-+qsin()aq

7、gsin第2页共12页IOI2004国家集训队论文金恺由于L和L’都是分割线，所以SABC=SA’B’C，即11AC×BCsingg=×A¢¢CBCsin22ÛAC×BC=×A¢¢CBCLLsinbasinLL¢¢sin()b-+qsin()aqÛ=singsingsinggsin2Lsin(b-+q)sin()aqÛ=L¢2sinbasin1pi>ba>>0-éùëûcos(b+a)-cos2()b--aqpi>ba->0=2-1éùcos(b+a)--cos()bacos(b-a-2q)

8、>-cos()baëû2cos(b+a)-cos2()b--aqcos(b+a)-cos2(b--aq)=>1cos(b+a)--cos()bacos(b+a)--cos()ba22所以L>L’，即L’α时，L不可能为最短的分割线。同理，当β<α时，L也不可能是最短的。若L是不过P的顶点的最短的分割线，那么L与P的两个夹角必然相等。这就是我们希望得到的，因为枚举L两个端点所在的边后，L的斜率就确