ex01.cpp

cut.c 给定一块宽度为W的矩形板

/*:1th experiment:[rectangle division]
//vesion 0.4 2005-11-17
//Pro. will creat out file result.htm to show result 
*/
#include <iostream>
#include <string>
#include <fstream>
#include <time.h>
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#define BW 50         //木板宽度 
#define MAXRECT 512
#define ERROR -1

using namespace std;

int BW=50;
int rectN;
int totalLen=0;					//保存最大长度 
int cutstart=0;
int cMethodNum=0;                 //还未切割的矩形数组的起始元素下标 
int n;	int &cutend=n;
struct rect {                   //矩形结构  x0.x1,y0.y1表示切割后在木板上的位置
    int position;               //标志这是第position个矩形 
	int height;
	int width;
	int x0,x1;
	int y0,y1;
	//bool cuted;               //cuted 的rectangle 自动调换到数组的前面  
} ;
//initialization MAXRECT 个rectangle结构 
//若要节省空间 可定义指针 
struct rect rects[MAXRECT];         
//struct rect *ptr; using cutstart.

int lcut(int x0,int x1,int y0,int y1);  //在小矩形内切割矩形的函数 
int gethighest(int start,int end);      //在剩下矩形中取最高的 
int getwidest(int start,int end);
int cut(int low,int method);                       //在无限长的矩形内切割矩形的函数 
int getlikely(int w ,int h ,int start ,int end );  //在剩下矩形中取合适的 
int getlikely2nd(int w,int h,int start,int end);
int printresult(void);                  //打印结果 
int ofile(char *fname,int top);
int main()
{	

    int inputn;
	printf("input numbers of rectangle please:");
	while(scanf("%i",&inputn)==0){
		printf("error,you had input %c ,you need input the number.",getchar());
	}
	if (inputn > MAXRECT){
		cout << "I am sorry that your input is larger than MAXRECT:" << MAXRECT
			<< endl;
		return -1;
 		}
	
 	rectN=inputn;
	n=--inputn;                           //数组下标n比输入大小inputn小 1 
	puts("input Borad Width please");
 	cin >> BW;
 	cout << "Now BW is " << BW <<endl;
  	for(int i=0;i<=n;i++){                //n 是最后一个数组下标 
	printf("please enter num %d rectangle's height and width orderly\n",(i+1));
	if(scanf("%d %d",&(rects[i].height),&(rects[i].width))==0) puts("error scanf rect h,w");
	if(rects[i].width > BW) {
		puts("error,width too long"); return 1;
	}
	rects[i].position=i+1;
	rects[i].x0=rects[i].x1=rects[i].y0=rects[i].y1=0;
	}
	
	struct method{
 	int methodN;
 	int totalLen;
  	}cMethod[2];
//init end
	for(int mNum=0;mNum < 2 ;mNum++){ 	//2 is the max method 
										//record every method's totallength
 	cMethodNum=mNum;
  	cutstart=0;
   	cut(0,mNum); //从底部开始 cut这时低坐标为 0 
	int top=0;
	for(int i=n;i>=0;i--){
    if (rects[i].y1>top) top=rects[i].y1;
    }
    totalLen=top;
	cMethod[mNum].methodN=mNum;
	cMethod[mNum].totalLen=totalLen;
 	}
 	if ((cMethod[0].totalLen) < (cMethod[1].totalLen)){
 		cMethodNum=0;
 		cutstart=0;
   		cut(0,0);
	}
  	else{ 
   		cMethodNum=1;
     	cutstart=0;
      	cut(0,1);
   		}
	printresult();
	system("pause");
	return 0;
}
int cut(int low,int method)
{
	if (low==0) cutstart=0;
    if(cutstart > cutend) {return 0;}     
    int precuti;			//restore cutstart
	int post;              // highest's position
 	post=gethighest(cutstart,cutend);
	struct rect rtemp;
	rtemp=rects[cutstart];rects[cutstart]=rects[post];rects[post]=rtemp;
	rects[cutstart].x0=0;
	rects[cutstart].x1=rects[cutstart].width+0;
	rects[cutstart].y0=low;
	rects[cutstart].y1=low+rects[cutstart].height;
	precuti=cutstart;			//restore cutstart
    cutstart++;
    //made a misktake hell!!!!!!! 
	lcut(rects[precuti].width,BW,low,low+rects[precuti].height);
    cut(low+rects[precuti].height,method);

    return 0;
}

int lcut(int x0,int x1,int y0,int y1)
{
	int post;
	int precuti; //被device 的那块 
	if(cutstart > cutend) return 0;
	if ((post=getlikely(x1-x0,y1-y0,cutstart,cutend))==-1)	return 0;
	struct rect rtemp;
	rtemp=rects[cutstart];rects[cutstart]=rects[post];rects[post]=rtemp;
	rects[cutstart].x0=x0;
	rects[cutstart].x1=rects[cutstart].width+x0;
	rects[cutstart].y0=y0;
	rects[cutstart].y1=y0+rects[cutstart].height;
	precuti=cutstart;
 	cutstart++;

 	if (cMethodNum == 0){ 
	/*上边子矩形长度度优先 */
  		lcut(rects[precuti].width+x0,x1,y0,y0+rects[precuti].height);
  		lcut(x0,x1,y0+rects[precuti].height,y1);
	}
	else {
 	/*右边子矩形高度优先 Now I guess,this is better*/
 		lcut(rects[precuti].width+x0,x1,y0,y1);        
	 	lcut(x0,rects[precuti].width+x0,y0+rects[precuti].height,y1);
	}
	return 0;
}
int gethighest(int start,int end)
{
    int highest=start;
	for(int i=start;i<=end;i++){
	   if (
		   (rects[i].height>rects[highest].height)|| 
    			((rects[i].height==rects[highest].height)&&
    	 		(rects[i].width>rects[highest].width))
	      )
           highest=i;
    }
	return highest;
}
int getwidest(int start,int end)
{
    int widest=start;
	for(int i=start;i<=end;i++){
	   if (
		   (rects[i].width>rects[widest].height)|| 
    			((rects[i].width==rects[widest].width)&&
    	 		(rects[i].height>rects[widest].height))
	      )
           widest=i;
    }
	return widest;
}
int getlikely(int w,int h,int start,int end)
{
//在剩余矩形中找比剩余木板小 且最高的矩形 
//    enum {off=-1,on}sign;
//    sign=off; 
    int highest=0;
    int likelyn=-1;
    int rh,rw;
	for(int i=start;i<=end;i++){
            rh=rects[i].height;
            rw=rects[i].width;
            if ((rh<=h)&&(rw<=w)==1){ 
                    //return i; //这样可直接返回 
                    if (rh > highest){
                    	likelyn=i;highest=rh;
                    }
                    else if((rh==highest) && (rw>rects[likelyn].width)){
                    	likelyn=i;highest=rh;
                    }
                    else ; //do nothing
            }
    }
    return likelyn;
}
int getlikely2nd(int w,int h,int start,int end)
{
//在剩余矩形中找比剩余木板小 且最高的矩形 
//    enum {off=-1,on}sign;
//    sign=off; 
    int widest=0;
    int likelyn=-1;
    int rh,rw;
	for(int i=start;i<=end;i++){
            rh=rects[i].height;
            rw=rects[i].width;
            if ((rh<=h)&&(rw<=w)==1){ 
                    //return i; //这样可直接返回 
                    if (rw > widest){
                    	likelyn=i;widest=rw;
                    }
                    else if((rw==widest) && (rh>rects[likelyn].height)){
                    	likelyn=i;widest=rw;
                    }
                    else ; //do nothing
            }
    }
    return likelyn;
}
int printresult(void)
{
	for(int i=0;i<=n;i++){
		printf("Rectangle %d:\nx0=%d x1=%d y0=%d y1=%d\n",
		i+1,rects[i].x0 ,rects[i].x1 ,rects[i].y0 ,rects[i].y1 );
	}
	int top=0;
	for(int i=n;i>=0;i--){
    if (rects[i].y1>top) top=rects[i].y1;
    }
    totalLen=top;
	printf("所需木板的总高度为:%d\n",top);
	ofile("result.htm",top);
	return 0;
}
int ofile(char *fname,int top)
{
	
	const int multiple=20;
	float times =1;
 	int atimes ;
  	
 	ofstream out(fname);
	string title="1th experiment[rectangle division]";
	string whatexp="//:Algorithms first experiment: Divide using small rectangle.";
 	//initialization heads
   	cout<< "Now,program is going to creat a html file,if display are not feat"
   		<< "you can change variable \"times\" or  enter a number between 1~10 here\n";
	cin >>  times;
	if ((times>0)&&(times<=10));
 	else {times =1;} 
 	atimes=int( multiple*times);
  	
    out << 	"<!--" 
    << "DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.01 Transitional//EN\" " << endl 
    << "\"http://www.w3.org/TR/html4/loose.dtd\" " << endl
    << "//:Just under Windows,with IE." << endl 
    << "\"" << whatexp << "\"" << "-->"<< endl
    << "<html>" << endl 
    << "<head>" << endl
    << "<meta http-equiv=\"Content-Type\" content=\"text/html; charset=gb2312\">"
    << endl
    << "<title>" << title 
    << " width of board:" << BW
    << " Nmubers of rectangle:" << rectN
    << " Total length:" << totalLen 
    << "</title>" << endl
    << "</head>" << endl
    << "<body>" << endl;
// init head end
// start content    
	out << "<div id=\"LayerBG\" style=\"position:absolute; left:0px; top:0px;"
 		<< "width:" << int(BW*atimes)
 		<< "px; z-index:1; height:" 
   		<< int (top*atimes) << "px; background-color:#dddddd;\"></div>"
 		<< endl;


	srand(time (0));
	int i;
 	for(i=0;i<=n;i++){
  	int color[6];	out <<i;
  	for (int j=0;j<6;j++) color[j]=(1 + rand() %0xC); //make rand color under CCCCCC
 	out << "<div id=\"LayeriCont" << int(i) << "\" style=\"position:absolute; "
  		<< "left:" << (int)rects[i].x0*atimes << "px; "
    	<< "top:"  << (int)rects[i].y0*atimes << "px; "
     	<< "width:"<< (int)rects[i].width*atimes << "px; "
      	<< "height:"<< (int)rects[i].height*atimes << "px; " 
       	<< "z-index:2; " 
        << "background-color: #" 
        << hex ;
        
    for (int j=0;j<6;j++) out << color[j]; 

    out << dec
        << ";\"></div>" 
        << endl;
   	out << "<div id=\"LayeriName" << int(i) << "\" style=\"position:absolute; "
  		<< "left:" << (int)rects[i].x0*atimes << "px; "
    	<< "top:"  << (int)rects[i].y0*atimes << "px; "
     	<< "width:"<< (int)rects[i].width*atimes << "px; "
      	<< "height:"<<(int)rects[i].height*atimes << "px; " 
       	<< "z-index:3; " 
       	<< "\"><p><h6>第" << rects[i].position << "块"
        << " w="  << rects[i].width 
        << " h="  << rects[i].height
        << " x0=" << rects[i].x0 //<< " x1=" << rects[i].x1
        << " y0=" << rects[i].y0 //<< " y1=" << rects[i].y1
        << "</h6></p></div>" 
        << endl;
        
        
        

        
        
        
 	}
// add sign of "end"
    out << "</body>" <<endl
    	<< "</html>" <<endl;
   	return 0;
}