HDU2050 由直线分割平面推广到折线分割平面

直线分割平面问题:

加入已有n-1条直线,那么再增加一条直线,最多增加多少个平面?

为了使增加的平面尽可能的多,我们应该使新增加的直线与前n条直线相交,且不存在公共交点。那么我们可以将新增加的这条直线分为:n-2条线段,和2条射线,每个线段和射线都可以将原有的平面一分为二,所以新增加的平面数目为:(n-2)+2;

折线分割平面问题:

同理为了使新增加的平面尽可能的多,我们应该使新增加的折线的每条射线与之前已有的折线(每个折线有两条射线)都相交,且没有公共交点。那么新增的折线中的每条射线将会被分为2*(n-1)条线段和1条射线,那么一条折线就会增加2*(2*(n-1))条线段和2条射线,但是两条平行的直线如果一段闭合形成了折线,那么将会减少一个区域,所以新增平面的数目为:4*(n-1)+1。

应该很明白了,代码不再贴出

原文地址:https://www.cnblogs.com/alan-W/p/5749327.html