最后代码.cpp

集装箱的装箱问题 给定一个集装箱

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1000 //表示木材的最大个数
#define INFINITY 10000


						#define SETN	360		//这个用来设置放木材的精度,为整型,理论上值越大,空间利用率越高,最大值最好不要超过360

							//我在这把它设置成360,以增加它的精度,请勿超过360度,否则系统可能奔溃



	double pos[MAX][2],r[MAX];			//pos[i][0]表示第i个木材的x坐标，pos[i][1]表示第i个木材的y坐标
	double tmp[MAX][2];			//这个用于判断当前块该放在哪里

	double x[MAX],y[MAX];
	int i,j,k,n,pid;
	double w,h,l;
	char str[50];
	double arcCompute=3.1415926*2/SETN; 
	int visited[MAX]={0};
bool cmp(const double &a,const double &b);

void Generate(int i,int j,int k,int pid){
	double x1,y1,r1,r2;
	x1=pos[i][0];	y1=pos[i][1];
	r1=r[i];	r2=r[j];
	x[pid]=x1+(r1+r2)*cos(k*arcCompute);
	y[pid]=y1+(r1+r2)*sin(k*arcCompute);
}


int CheckOK(int pid,int i){			//I代表将要放进去的节点
	int j;
	double x11,y11;
	x11=x[pid];
	y11=y[pid];
	if((x11+r[i])>w+0.001||(y11+r[i])>h+0.001||x11-r[i]+0.0001<0||y11-r[i]+0.0001<0) return 0;
	for(j=1;j<i;j++){
		if(visited[j]==0) continue;
		if((x11-pos[j][0])*(x11-pos[j][0])+(y11-pos[j][1])*(y11-pos[j][1])+0.001<(r[j]+r[i])*(r[j]+r[i]))		//加0.001是防止浮点数的计算误差,因为两个浮点数比较大小如:1.000001 1.000002计算中的舍入误差可能会出现差错
			return 0;
	}
	return 1;
}
int main(){
	int flag,minyPos,start;
	double miny,sum;
	printf("输入文件名:\n");
	scanf("%s",str);
	if(freopen(str,"r",stdin)==NULL){
		printf("文件无法打开\n");
		exit(1);
	}

	scanf("%d %lf %lf %lf",&n,&w,&h,&l);
	for(i=1;i<=n;i++){
		scanf("%lf ",&r[i]);
//		printf("%lf ",r[i]);
	}


	sort(r+1,r+n+1,cmp);
	

	for(start=1;start<=n;start++){
		if(r[start]*2+0.0001<w&&r[start]*2+0.0001<h){
		pos[start][0]=r[start];
		pos[start][1]=r[start];
		visited[start]=1;
		break;
		}
	}
	printf("能放进去的编号	半径	坐标X	坐标Y\n");
	printf("%d		%lf %lf %lf\n",start,r[start],pos[start][0],pos[start][1]);
	for(i=start;i<=n;i++){
		pid=1;
		for(j=1;j<i;j++){
			if(visited[j]==1)
			for(k=0;k<=SETN;k++){
				flag=1;
				Generate(j,i,k,pid);
				if(CheckOK(pid,i)==0){
					x[pid]=INFINITY;
					y[pid]=INFINITY;
					flag=0;
				}
				if(flag==1) pid++;
			}
		}
		
		miny=INFINITY;			//这里的miny主要是指最下面的位置开始放起
		minyPos=1;
		for(k=1;k<pid;k++)
			if(miny>y[k]){
				minyPos=k;
				miny=y[k];
				pos[i][0]=x[k];
				pos[i][1]=y[k];
			}

			if(pid!=1)	{
				printf("%d		%lf %lf %lf \n",i,r[i],x[minyPos],y[minyPos]);
				visited[i]=1;
			}

	}
	
	
		//空间利用率的计算问题
	sum=0;
	for(i=1;i<=n;i++)
		if(visited[i]==1) sum+=3.1415926*r[i]*r[i];
	printf("在精度是%d一共用了的面积是:%lf \n",SETN,sum);
	printf("空间占有率是:%lf	\n",sum/(w*h));
			

//	下面这一段是写出数据,以备Java 画图来用的.
	freopen("sort.txt","w",stdout);
	for(i=1;i<=n;i++)
		if(visited[i]==0)	printf("0,");
		else printf("%.3lf,",r[i]);
		printf("\n");
	for(i=1;i<=n;i++)
		if(visited[i]==0)	printf("0,");
		else printf("%.3lf,",pos[i][0]);
		printf("\n");
	for(i=1;i<=n;i++)
		if(visited[i]==0)	printf("0,");
		else printf("%.3lf,",pos[i][1]);
		printf("\n");
	return 0;
}

bool cmp(const double &a,const double &b){
	return a>b;
}