05 Apr 10 WHU2010校赛预赛C题：Ice-sugar Gourd

题目大意：给一个由两种水果组成的冰糖葫芦，现在需要把这两种水果平均送给两个人。问最少需要切割多少次。（切割不能把水果切开）

这题是我出的，在这里说一下做法：如果能够猜到一个结论：最多需要切割两次。

那这个题就很简单了。。

说一下证明：

这里的证明要用到计算几何里面很重要的一个问题：给平面上的两种点，一定存在一条直线，把这两种点分别均分。

那么怎么应用到我们这个题目里面呢？就是想象把冰糖葫芦弯曲成一个抛物线。根据上面的结论，我们一定可以把这个抛物线用一条直线切割开来。这条直线与抛物线最多有两个交点-.-所以问题得证。。

Filed in Iproblem

code6 | 08 Apr 2010 7:09 pm
求”计算几何里面很重要的一个问题”的出处或证明,thx

[Reply]
momodi Reply:
April 18th, 2010 at 2:58 pm
wikipedia上有。。

[Reply]