circles.h

回溯算法中的圆排列问题

#ifndef Cir
#define Cir
#include"math.h"
template<class T>class Circles
{
public:
	Circles(T nn,T rr[]);
	void backtrack(int t);
	float center(int t);
	void compute();
	~Circles();
	void print();
private:
	void Swap(T &a,T &b);
	int n;
	T min;
	T *x;
	T *r;
};
template<class T> Circles<T>::Circles(T nn,T *rr)
{
	n=nn;
	min=100000;
	x=new T[n+1];
	r=rr;	
}

template<class T>Circles<T>::~Circles()
{
	delete [] x;
}

template<class T>void Circles<T>::Swap(T &a,T &b)
{
	T temp=a;
	a=b;
	b=temp;
}

template<class T>void Circles<T>::backtrack(int t)
{
	if(t>n)
		compute();
	else
		for(int j=t;j<=n;j++)
		{
			Swap(r[t],r[j]);
			float centerx=center(t);
			if(centerx+r[t]+r[1]<min)
			{
				x[t]=centerx;
				backtrack(t+1);
			}
			Swap(r[t],r[j]);
		}
}

template<class T>float Circles<T>::center(int t)
{
	float temp=0;
	for(int j=1;j<t;j++)
	{
		float valuex=(float)(x[j]+2.0*sqrt(r[t]*r[j]));
		if(valuex>temp)
			temp=valuex;
	}
	return temp;
}

template<class T>void Circles<T>::compute()
{
	float low=0,
		  high=0;
	for(int i=1;i<=n;i++)
	{
		if(x[i]-r[i]<low)
			low=x[i]-r[i];
		if(x[i]+r[i]>high)
			high=x[i]+r[i];
	}
	if(high-low<min)
		min=high-low;
}

template <class T> void Circles<T>::print()
{
	for(int i=1;i<=n;i++)
		cout<<x[i]<<ends;
	cout<<endl;
	cout<<min<<endl;
} 

#endif