首页 > ACM题库 > HDU-杭电 > HDU 3843-Magic Sticks[解题报告]HOJ
2015
04-13

HDU 3843-Magic Sticks[解题报告]HOJ

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.

Machine Works

输入:

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