2015
04-13

# Magic Sticks

Magic was accepted by all ancient peoples as a technique to compel the help of divine powers. In a well-known story, one group of sorcerers threw their walking sticks on the floor where they magically appeared to turn into live serpents. In opposition, another person threw his stick on the floor, where it turned into a serpent which then consumed the sorcerers’ serpents!

The only magic required for this problem is its solution. You are given a magic stick that has several straight segments, with joints between the segments that allow the stick to be folded. Depending on the segment lengths and how they are folded, the segments of the stick can be arranged to produce a number of polygons. You are to determine the maximum area that could be enclosed by the polygons formed by folding the stick, using each segment in at most one polygon. Segments can touch only at their endpoints. For example, the stick shown below on the left has five segments and four joints. It can be folded to produce a polygon as shown on the right.

The input contains several test cases. Each test case describes a magic stick. The first line in each test case contains an integer n (1 <= n <= 500) which indicates the number of the segments in the magic stick. The next line contains n integers S1,S2, . . . , Sn (1 <= Si <= 1000) which indicate the lengths of the segments in the order they appear in the stick.
The last test case is followed by a line containing a single zero.

The input contains several test cases. Each test case describes a magic stick. The first line in each test case contains an integer n (1 <= n <= 500) which indicates the number of the segments in the magic stick. The next line contains n integers S1,S2, . . . , Sn (1 <= Si <= 1000) which indicate the lengths of the segments in the order they appear in the stick.
The last test case is followed by a line containing a single zero.

4
1 2 3 4
8
3 4 5 33 3 4 3 5
0

Case 1: 4.898979
Case 2: 19.311

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

const double pi = acos(-1.);
const double eps = 1e-8;

using namespace std;

int N;
int a[1000];
double ang[1000];

int dcmp( double x )
{
if( x < eps )	return -1;
if( x > eps )	return 1;
return 0;
}

bool chk( int s, int e, double R )
{
double t = 2*R*R;
double sA = 0, mA = -1e30;
int id;
for( int i = s; i < e; ++i )
{
ang[i] = acos((t-a[i]*a[i])/t);
sA += ang[i];
if( mA < ang[i] )
mA = ang[i], id = i;
}

if( dcmp(sA-mA-pi) >= 0 )
return dcmp(sA-2*pi) <= 0;
else
{
ang[id] *= -1;
return dcmp(sA-mA+2*pi-mA - 2*pi) >= 0;
}
}

int cal( int s, int e, double& S )
{
double ll = 0, rr = 1000000, R;

for( int i = s; i < e; ++i )
ll = max(ll, a[i]*0.5);

for( int T = 0; T < 80; ++T )
{
R = (ll+rr)/2;
if( chk(s, e, R) )
rr = R;
else
ll = R;
}
R = (ll+rr)/2;

S = 0;
for( int i = s; i < e; ++i )
S += R*R*sin(ang[i]);
S *= 0.5;

for( int i = s; i < e; ++i )	if( ang[i] < 0 )
return i;
return -1;
}

double f( int s, int e )
{
if( e-s < 3 )	return 0;

int sum = 0, mv = a[s];
int i, j, k, id = s;
for( i = s; i < e; ++i )
{
sum += a[i];
if( a[i] > mv )
mv = a[i], id = i;
}

if( sum <= mv*2 )
return f(s, id)+f(id+1, e);
else
{
double S;
k = cal(s, e, S);
if( k < 0 )
return S;
return max(S, f(s, k)+f(k+1, e));
}
}

int main()
{
int i, cases = 1;

while( scanf("%d", &N), N )
{
for( i = 0; i < N; ++i )
scanf("%d", &a[i]);
printf("Case %d: %.8lf\n", cases++, f(0, N));
}

return 0;
}

1. 今看二叨的话，知道你是爱表白，乐观，重友谊，谁都希望获救和被重新定注，祝福话是温暖的担·但愿有能接受的结果。二叨学了几道有新意菜，有空与小友聚聚，舒缓心情

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧