7964: BZOJ3964:[WF2011]magicsticks

Memory Limit:256 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

对于古代居民来说,魔法是一种借助神力的技术。在一个有名的故事里魔杖,一 群男巫把他们的魔杖扔在地上,这些魔杖神奇地变成了活生生的蛇。然而,另一 个人将他的魔杖扔在地上时,它变成的蛇则吃掉了男巫们的蛇! 男巫们为了对付这个蛋疼的事情,需要解决以下问题:你有一根魔棒,它是一条 由若干条给定长度的线段组成的折线,折线的所有顶点都可以任意折叠。这条折 线通过折叠可以围成若干个多边形。你需要最大化这些多边形的面积之和,注意 ,折线上的每一条线段都至多被用于一个多边形。线段只能在它们的端点上相交 。 左图的折线由五条线段和四个可折叠的轴组成,它可以被折叠成右图那样的多边 形。


输入格式

输入的第一行一个整数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

请不要提交,尚无SPJ


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: