BZPRO
#3964. [WF2011]magicsticks
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
对于古代居民来说，魔法是一种借助神力的技术。在一个有名的故事里魔杖，一
群男巫把他们的魔杖扔在地上，这些魔杖神奇地变成了活生生的蛇。然而，另一
个人将他的魔杖扔在地上时，它变成的蛇则吃掉了男巫们的蛇！
男巫们为了对付这个蛋疼的事情，需要解决以下问题：你有一根魔棒，它是一条
由若干条给定长度的线段组成的折线，折线的所有顶点都可以任意折叠。这条折
线通过折叠可以围成若干个多边形。你需要最大化这些多边形的面积之和，注意
，折线上的每一条线段都至多被用于一个多边形。线段只能在它们的端点上相交
。
左图的折线由五条线段和四个可折叠的轴组成，它可以被折叠成右图那样的多边
形。
输入格式
输入的第一行一个整数n，表示这条折线包含的线段数。
下一行共n个数，顺次给出每条线段的长度s1,s2,...,sn
输出格式
一个实数表示多边形的最大面积和
样例
样例输入
4
1 2 3 4
8
3 4 5 33 3 4 3 5
0
样例输出
Case 1: 4.8989794820
Case 2: 19.3111795107
数据范围与提示
3<=n<=500, 1<=si<=1000
BZPRO