load.cpp

(1).问题描述：集装箱的装箱问题 给定一个集装箱

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<windows.h>
#include<time.h>


#define BI 1e-5
#define bp 3.14159	//圆周率
#define x0 20		
#define y0 25		//原点坐标

double W;   //集装箱宽
double H;	//集装箱高
double L;	//集装箱长
int n;		//木材数目
int count=0;	//记录装入的木材数目
int right;

typedef struct{
	//木材
	double x,y,r;
	int mark;
}Lig;

Lig *la;

//--------------------------------------------------------------------------
int ReadFile(){
	//读入测试文件，并对相应变量进行初始化
	int i;
	char filename[30];
	printf("Please input the file name:\n");
	scanf("%s",&filename);
	freopen(filename,"r",stdin);
	scanf("%d %lf %lf %lf",&n,&W,&H,&L);
	printf("n=%d\n",n);
	printf("W=%lf\n",W);
	printf("H=%lf\n",H);
	printf("L=%lf\n",L);
	la=(Lig *)malloc(sizeof(Lig)*(n+1));
	for(i=1;i<=n;i++){
		scanf("%lf",&la[i].r);
		la[i].mark=0;
	}//for
	return 1;
}//Load

//----------------------------------------------------------------------------
void InsertionSort(){
	//对木材按照半径由大到小进行插入排序
	int i,j;
	double key;
	for(i=2;i<=n;i++){
		key=la[i].r;
		for(j=i-1;j>0;j--)
			if(la[j].r<key){
				la[j+1].r=la[j].r;
			}//if
			else
				break;
		la[j+1].r=key;
	}//for
}//InsertionSort

//----------------------------------------------------------------------------
double Distance(double x1,double y1,double x2,double y2){
	//求两点之间的距离
	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}//Distance
//----------------------------------------------------------------------------
int Test(int cl,double cx,double cy){
	//测试对于当前的木材（la[cl]），给出圆心位置(cx,cy)，是否能够将该木材装入
	//若能，返回1；否则，返回0
	int i;
	if(cx+la[cl].r>W+BI || cy+la[cl].r>H+BI || cx<la[cl].r-BI || cy<la[cl].r-BI)
		return 0;
	else{
		for(i=1;i<cl;i++)
			if(la[i].mark==1)
				if(Distance(la[i].x, la[i].y, cx, cy)<la[i].r+la[cl].r-BI)
					//两圆相交
					return 0;
		return 1;
	}//else
}//Test
//----------------------------------------------------------------------------
void TryTo(int crtlig){
	//测试能否将该木材（la[cl]）装入集装箱
	int i,j;
	double rsum,crtx,crty;

	rsum=la[right].r+la[crtlig].r;		//测试是否能先放右下方
	for(j=0;j<=90;j++){
		crtx=la[right].x + rsum * cos(-bp/2.0 + j*bp/180.0);
		crty=la[right].y + rsum * sin(-bp/2.0 + j*bp/180.0);
		if(Test(crtlig,crtx,crty)==1){
			//这样的圆心坐标能放下该木材（la[crtlig]）
			la[crtlig].x=crtx;
			la[crtlig].y=crty;
			la[crtlig].mark=1;
			count++;
			right=crtlig;
			return;
		}//if
	}//for
	for(i=1;i<crtlig;i++)
		//尽量放在左边
		if(la[i].mark==1){
			rsum=la[i].r+la[crtlig].r;
			for(j=0;j<360;j++){
				crtx=la[i].x + rsum * cos(-bp/2.0 + j*bp/180.0);
				crty=la[i].y + rsum * sin(-bp/2.0 + j*bp/180.0);
				if(Test(crtlig,crtx,crty)==1){
					//这样的圆心坐标能放下该木材（la[crtlig]）
					la[crtlig].x=crtx;
					la[crtlig].y=crty;
					la[crtlig].mark=1;
					count++;
					return;
				}//if
			}//for
		}//if
}//TryTo

//----------------------------------------------------------------------------
void Load(){
	//用贪心算法将木材装入集装箱，让利用率尽可能高
	int i,j;
	for(i=1;i<=n;i++)
		if(la[i].r<=W/2.0 && la[i].r<=H/2.0){
			//选取第一个满足条件的木材
			la[i].x=la[i].y=la[i].r;
			la[i].mark=1;
			right=i;
			count++;
			break;
		}//if
	for(j=i+1;j<=n;j++){
		TryTo(j);
	}//for
}//Load

//-----------------------------------------------------------------------------
int Mag(double source){
	//放大坐标
	int result;
	result=(int) (source*20);
	return result;
}//Mag
//-----------------------------------------------------------------------------
double Shift(double symmetry,double sy){
	//求sy关于对称轴symmetry的对称纵坐标
	return (2*symmetry-sy);
}//Shift

//-----------------------------------------------------------------------------
void DrawGragh(){
	int i,choose=0;
	double sym;	//对称轴
	double y1,y2,yr;
	char *M[36]={"0'\0'","1 ","2 ","3 ","4 ","5 ","6 ","7 ","8 ","9 ","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34","35"};
	HDC hdc = GetWindowDC( GetDesktopWindow() );			// 获取一个可供画图的DC,此处用桌面
	HPEN hpen1 = CreatePen( PS_SOLID, 1, RGB(255,0,0) );	// 创建红色1像素宽度的实线画笔
	HPEN hpen2 = CreatePen( PS_SOLID, 1, RGB(0,255,0) );	// ....绿色...................
	HBRUSH hbrush1 = CreateSolidBrush( RGB(0,0,255) );		// 创建一个实体蓝色画刷
	HBRUSH hbrush2 = CreateSolidBrush( RGB(255,255,0) );	// ............黄色....
	HBRUSH hbrush3 = CreateSolidBrush( RGB(128,0,128) );	// ............紫色....
	HBRUSH hbrush4 = CreateSolidBrush( RGB(255,165,0) );	// ............橙色....
	HBRUSH hbrush5 = CreateSolidBrush( RGB(255,20,147) );	// ............深粉色..
	HBRUSH hbrush6 = CreateSolidBrush( RGB(0,128,0) );		// ............纯绿色..
	HBRUSH hbrush7 = CreateSolidBrush( RGB(238,130,238) );	// ............紫罗兰..
	HPEN hpen_old = (HPEN)SelectObject( hdc, hpen2 );       //将hpen2选进HDC,并保存原来的画笔
	Rectangle( hdc, Mag(x0), Mag(y0), Mag(x0+W), Mag(y0+H) );                //画集装箱
	sym=(y0+(y0+H))/2;
	HBRUSH hbrush_old = (HBRUSH)SelectObject( hdc, hbrush1 );	// 将hpen1选进HDC，并保存HDC原来的画刷
	for(i=1;i<=n;i++){
		switch(choose%7){
			//选择颜色
			case 0:	SelectObject( hdc, hbrush1 ); break;
			case 1:	SelectObject( hdc, hbrush2 ); break;
			case 2:	SelectObject( hdc, hbrush3 ); break;
			case 3:	SelectObject( hdc, hbrush4 ); break;
			case 4:	SelectObject( hdc, hbrush5 ); break;
			case 5:	SelectObject( hdc, hbrush6 ); break;
			case 6:	SelectObject( hdc, hbrush7 ); break;
		}//switch
		if(la[i].mark==1){
			choose++;
			y1=Shift(sym,y0+la[i].y-la[i].r);
			y2=Shift(sym,y0+la[i].y+la[i].r);
			yr=Shift(sym,y0+la[i].y);		//相应的坐标变换
			Ellipse( hdc, Mag(x0+la[i].x-la[i].r), Mag(y1), Mag(x0+la[i].x+la[i].r), Mag(y2) );	//画圆
			TextOut( hdc, Mag(x0+la[i].x), Mag(yr), M[i], 2);	//给圆标上号数
			Sleep(1500);	//隔1.5s装入一个木材，动态演示
		}//if
	}//for
	for(i=n;i>0;i--)
		if(la[i].mark==1){
			TextOut( hdc, Mag(x0+la[i].x), Mag(yr), M[i], 2);
			break;
		}//if
}//DrawGragh

//-----------------------------------------------------------------------------
void main(){
	LARGE_INTEGER litmp;
	LARGE_INTEGER liCount1;   
	LARGE_INTEGER liCount2;
	double dfFreq;
	QueryPerformanceFrequency(&litmp);
	dfFreq = (double)litmp.QuadPart;
	double proportion,area=0;
	int i,choose=0;

	if(!ReadFile())
		printf("Read file error!!");	//读入测试文件

	InsertionSort();	//对木材按照半径由大到小进行插入排序

	QueryPerformanceCounter(&liCount1);		//调用时间函数

	Load();		//用贪心算法进行求解

	QueryPerformanceCounter(&liCount2);

	printf("The container load %d lignums in all\n",count);
	for(i=1;i<=n;i++)
		if(la[i].mark==1){
			area+=bp*la[i].r*la[i].r;
			choose++;
			printf("The %dst lig:r=%lf,x=%lf,y=%lf    i=%d\n",choose,la[i].r,la[i].x,la[i].y,i); //给出装入的木材的信息
		}//if
	printf("The area used is:%lf\n",area);
	printf("The total area of the container is:%lf\n",W*H);
	proportion=area/(W*H);
	printf("The proportion the space of container used is:%f\n",proportion);	//给出程序求得的利用率

	printf("Running Time=%f  seconds\n",(double)(liCount2.QuadPart -liCount1.QuadPart )/dfFreq);//给出程序运行时间

	DrawGragh();//画图
}//main