来自"NOCOW"

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是URAL Volume 1 中的OI题目Chocolate的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

目录 1 题目叙述 2 算法复杂度 3 算法叙述 4 补充证明

[编辑] 题目叙述

有一个凸N边形，3<=n<=50，顶点的坐标范围为-100到100的实数，求最短的割痕使得分成的两部分面积相等。

[编辑] 算法复杂度

时间复杂度 O(n²)

空间复杂度 O(n)

[编辑] 算法叙述

以下用S表示此多边形的总面积，S(A)表示A部分的面积，表示p到q的直线距离。

可以看到，最优解一定在以下两种情况中：(蓝色直线为切痕)

在a)中，枚举经过的顶点(图中的P点)，然后顺着多边形走，肯定会找到某条边(图中的绿色边)，使得S(A)和S(B)都小于0.5*S，则：

根据S(1)和S(2)的比(和三角形面积公式)就可以算出切痕和多边形的另一个交点，从而得到切痕长。

下面重点说明b)这种情况。首先，可以证明(在后面)，∠1=∠2。所以算法分为以下几步：

1. 找到PQ的斜率，设为k。这个我是先计算两条绿边的倾斜角，再取平均数，再取正切值得到的。注意：区分内角平分线和外角平分线！
2. 过这两条边的四个端点作四条斜率为k的直线，选其中两条(与两条绿边交于两点的)，即图中红色的线，如果不存在这样的线，则说明此情况无解。设依次交于a,b,c,d四点(如图)。
3. 计算S(A)和S(B)，注意不要丢掉“多余的一小条”。同上，可以得出S(1)和S(2)。
   • 当S(2)=0时，P,Q分别与b,c重合，
   • 当时，令，根据梯形面积公式，切痕长度

在所有的PQ中找到最小值即可。

[编辑] 补充证明

b)中∠1=∠2的证明：即证明以下命题：

已知∠OAB=α，OP平分∠OAB交AB于P，OP⊥AB(∴∠OAB=∠OBA)，CD交AB于H，，求证：

证明： 作CM⊥OP于M，DN⊥OP于N，CD交OP于K，

则，，

又∵，，

∴

∴

∴

根据均值不等式，有

而

∴

命题得证。