greedy.cpp

给定一个集装箱

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

#define M 36
#define pi 3.1415926

double H,W,L;
int Columnum;

struct CR
{
	double x,y,r;
	int sel;
}cr[M];

int count;  //计算装进去的个数


double dis(CR a,double x,double y) //两个圆圆心间的距离
{
	return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y));
}

int sort(CR *obj,int n)//按照圆柱的半径由大到小排序
{
	CR a;
	int j;
	for(int i=0;i<Columnum;i++)
	{ 
		a=obj[i];
		j=i-1;
		while(j>=0 && obj[j].r<a.r)
		{
			obj[j+1]=obj[j];
			j=j-1;
		}
		obj[j+1]=a;
	}
	return 0;
}

bool put(int now,double tx,double ty)//判断在(tx,ty)这个位置是否可以放下
{
	if(tx<cr[now].r || tx+cr[now].r>W || ty<cr[now].r || ty+cr[now].r>H)
		return false; //越界
	for(int i=0;i<now;i++)
		if(cr[i].sel)//判断是否和别人相交
			if(dis(cr[i],tx,ty)<cr[i].r+cr[now].r/*-E*/) //相交
				return false;
	return true;
}

void check(int now)//对于第now个 找放置的位置
{  
	double t,dx,dy;
	for(int i=0;i<now;i++)
		if(cr[i].sel)//对每个已插入的
		{
			t=cr[i].r+cr[now].r;
			for(int j=0;j<360; j++)//对每个角度进行检查
			{ 
				dx=cr[i].x+t*cos(-pi/2.0 + j*pi/180.0);
				dy=cr[i].y+t*sin(-pi/2.0 + j*pi/180.0);
				if(put(now,dx,dy)==true)//找到合适位置了
				{ 
					count++;
					cr[now].x=dx;
					cr[now].y=dy;
					cr[now].sel=1;
					return ;
				}
			}
		}
}


void Gdy()
{
	count=0;
	for(int i=0;i<Columnum;i++) //初始化
		cr[i].sel=0; 
	for(i=0;i<Columnum;i++)
	{
		if(count==0 && cr[i].r <= H/2 &&cr[i].r <=W/2)//第一个能放进的
		{
			cr[i].x=cr[i].r;
			cr[i].y=cr[i].r;
			cr[i].sel=1;
			count++;
		}
		else
			check(i);  //检查其他的
	}
}

void draw()
{
	double temp;
	int t;
	char *S[M]={"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"};
	HBRUSH hbrush_old;
	HDC hdc = GetWindowDC( GetDesktopWindow() );
	HPEN hpen1 = CreatePen( PS_SOLID, 1, RGB(255,200,200) );// 创建浅色1像素宽度的实线画笔  
	HPEN hpen2 = CreatePen( PS_DASH, 5, RGB(0,255,0) ); // 创建绿色5像素宽度的破折画笔
	HBRUSH hbrush1 = CreateSolidBrush( RGB(0,0,255) ); // 创建一个实体蓝色画刷 
	HBRUSH hbrush2 = CreateSolidBrush( RGB(128,0,255) ); //紫色 
	HBRUSH hbrush3 = CreateSolidBrush( RGB(0,255,64) );//绿色
	HBRUSH hbrush4 = CreateSolidBrush( RGB(128,255,0) );//
	HBRUSH hbrush5 = CreateSolidBrush( RGB(255,0,128) );//紫色
	HPEN hpen_old = (HPEN)SelectObject( hdc, hpen1 );
	hbrush_old = (HBRUSH)SelectObject( hdc, hbrush1);
	Rectangle(hdc, 200, 400, 200+(int)(W*20), 400-(int)(H*20) ); 
	for(int i=0;i<Columnum;i++)
	{
		if(i%4==0)
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush2);
		else if(i%4==1)
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush3);
		else if(i%4==2)  
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush4);
		else
			hbrush_old = (HBRUSH)SelectObject( hdc, hbrush5);
		if(cr[i].sel)
		{
			t=i;
			Ellipse( hdc,(int)(200+20*(cr[i].x-cr[i].r)), (int)(400-20*(cr[i].y+cr[i].r)), (int)(200+20*(cr[i].x+cr[i].r)), (int)(400-20*(cr[i].y-cr[i].r)) );//画圆
			TextOut( hdc,(int)(200+20*cr[i].x),(int)(400-20*cr[i].y),S[i+1],2); //i,signed i+1; 并用数字标记
		}
	}
	TextOut( hdc,(int)(200+20*cr[t].x),(int)(400-20*cr[t].y),S[t+1],2); //最后一个
}

void main()
{
	FILE *fp;
	char filename[20];
	long start; //计时
	double area =0;
    int i;
	printf("\n  Please input the file name:"); //读入文件
	scanf("%s",filename);
	if((fp=fopen(filename,"r"))==NULL)
    {
        printf("\n  The file is not exist!\n\n  ");//文件不存在则退出/
        exit(0);
    }
	start=GetTickCount();
	fscanf(fp,"%d",&Columnum);
	fscanf(fp,"%lf%lf%lf",&W,&H,&L);
	for(i=0;i<Columnum;i++)	
			fscanf(fp,"%lf",&cr[i].r);	
	sort(cr,Columnum); //排序
	Gdy();  //主体函数
	for(i=0;i<Columnum;i++) //计算占有面积
			if(cr[i].sel) 
				area += pi*cr[i].r*cr[i].r; 
	draw(); //作图
	printf("  资源利用率为: %lf\n",area/(W*H));
	printf("  程序运行时间为: %f 秒\n  ",(GetTickCount()-start)/1000.0);	
}