UVa10012 - How Big Is It

UVa10012 - How Big Is It?

题目地址：点击打开链接

这个题的困难就是已经知道一组球的全排列了，怎么求包围该组球的最小的矩形的长度。

首先确定每个球圆心的位置：

要想使包围的矩形最小，球都是尽可能的与其他球接触的

如果两个球a,b接触，那么position[b]=position[a]+2*sqrt(rad[a]*rad[b])

第i个球的圆心的位置

为max(position[j]+2*sqrt(rad[j]*rad[i])

其中j=0,1,...,i-1

现在确定了球的圆心位置之后，这组球的最左边可以到到：

min(position[i]-rad[i])

最右边可以达：

max(position[i]+rad[i])

所以矩形边长 为

max(position[i]+rad[i])-min(position[i]-rad[i])

#include <iostream>
#include <cmath>
#include <limits>
#include <iomanip>
#include <algorithm>
using namespace std;
double rad[10];
int num[10];
int n;
double min_length;
void check()
{
	double position[10];
	position[0]=0;
	for(int i=1;i<n;++i)
	{
		double temp=numeric_limits<double>::min();
		for(int j=0;j<i;++j)
		{
			double x=position[j]+2*sqrt(rad[num[j]]*rad[num[i]]);
			if(x>temp)
				temp=x;
		}
		position[i]=temp;
	}
	double min_position=numeric_limits<double>::max();
	double max_position=numeric_limits<double>::min();
	for(int i=0;i<n;++i)
	{
		if(position[i]-rad[num[i]]<min_position)
			min_position=position[i]-rad[num[i]];
		if(position[i]+rad[num[i]]>max_position)
			max_position=position[i]+rad[num[i]];
	}
	if(max_position-min_position<min_length)
		min_length=max_position-min_position;
}
int main()
{
	int m;
	cin>>m;
	while(m--)
	{
		cin>>n;

		for(int i=0;i<n;++i)
		{
			cin>>rad[i];
			num[i]=i;
		}
		min_length=numeric_limits<double>::max();
		do 
		{
			check();
		} while (next_permutation(num,num+n));
		cout<<setiosflags(ios::fixed)<<setprecision(3)<<min_length<<endl;
	}
	return 0;
}