circle.cpp

算法设计中的经典问题

// Circle.cpp: implementation of the CCircle class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "符号三角形，n皇后，圆排列.h"
#include "Circle.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CCircle::CCircle()
{

}

CCircle::~CCircle()
{

}

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


void CCircle::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;
}

void CCircle::Backtrack(int t)
{
		float tempi;
	if(t>n)
		Compute();
	else
		for(int j=t;j<=n;j++)
		{
             tempi=r[t];
			 r[t]=r[j];
			 r[j]=tempi;
			 float centerx=Center(t);
			 if(centerx+r[t]+r[1]<min)
			 {
				 x[t]=centerx;
				 Backtrack(t+1);
			 }
			 tempi=r[t];
			 r[t]=r[j];
			 r[j]=tempi;
		}
}

float CirclePerm(int n,float *a)
{
	CCircle X;
	X.n=n;
	X.r=a;
	X.min=10000;
	float *x=new float[n+1];
	X.x=x;
	X.Backtrack(1);
	delete[]x;
//	cout<<X.r<<endl;
	return X.min;
}