lab_1.c

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

#include<graphics.h>
#include<stdio.h>
#include<time.h>
int num=0;/*for selecting num */
int k=0;/* for sorting */
int n,W=0;/* n for total num,  W for the total width */
struct Coordinate
{
    int x0,y0;/* 矩形左上角坐标 */
    int x1,y1;/* 矩形右下角坐标 */
};

int SearchBlock(int w,int a[][2],int h)/*for seaching the right block   */
{
    int i;
    for(i=0;i<n;i++)
        if((a[i][1]!=0)&&(a[i][0]<=w)&&(a[i][1]<=h))break;
    return i;
}


void Divide(int x0,int y0,int w,int a[][2],struct Coordinate zuobiao[],int h)

{  /*切割文件*/
    int l,i,temp;
    i=SearchBlock(w,a,h);
    if(i<n)
     {
        zuobiao[k].x0=x0;/* 保存坐标 */
        zuobiao[k].y0=y0-a[i][1];
        zuobiao[k].x1=x0+a[i][0];
        zuobiao[k].y1=y0;
        k++;
        printf("Divide the %d Block : %d %d\n",++num,a[i][1],a[i][0]);
        temp=a[i][1];
        a[i][1]=0;
        x0=x0+a[i][0];
        Divide(x0,y0,w-a[i][0],a,zuobiao,temp);/* 先递归右边 */
        x0=x0-a[i][0];
        y0=y0-temp;
        Divide(x0,y0,w,a,zuobiao,h-temp);/* 再递归上边 */

    }
}


void Sort(int a[][2])/*for sorting the arry by h */
{/* 冒泡排序按高度 */
    int key=1;
    int i,j,temp1,temp0;
    for(i=0;i<n&&key;i++)
    {
        key=0;
        for(j=0;j<n-i;++j)
        if(a[j][1]<a[j+1][1])
        {
            temp1=a[j][1];temp0=a[j][0];
            a[j][1]=a[j+1][1];a[j][0]=a[j+1][0];
            a[j+1][1]=temp1;a[j+1][0]=temp0;
            key=1;
        }

    }
}


void Print(int a[][2])
{
    int i;
    printf("%d %d\n",n,W);
    for(i=0;i<n;i++)
    printf("%d %d\n",a[i][1],a[i][0]);
}

void Show (struct Coordinate zuobiao[])
{  /*图形界面显示函数*/
     int gdriver,gmode,i,j;
     detectgraph(&gdriver,&gmode);
     initgraph(&gdriver, &gmode, "");
     setbkcolor(BLUE);
     setfillstyle(1,WHITE);
     setcolor(WHITE);
     bar(0,0,W,479);
     for(i=0;i<n;i++)
     {
         j=i+1;
         j=j%8; /* 文件颜色 */
         setfillstyle(1,j);
         setcolor(j);
         getch();
         bar(zuobiao[i].x0,zuobiao[i].y0,zuobiao[i].x1,zuobiao[i].y1);
     }
}

void main()
{
    int a[1000][2];
    int temp,i,H=0,x0,y0; /* H for the answer */
    FILE *fp;
    struct Coordinate zuobiao[200];
    clock_t start,end;
    start = clock();/* 开始时时间点 */


    if((fp=fopen("156.txt","rw"))==NULL)/* read .txt */
    {
        printf("Cannot open infile\n");
        return;
    }
    fscanf(fp,"%d %d",&n,&W);/* write ; */
    for(i=0;i<n;i++)
        fscanf(fp,"%d %d",&a[i][1],&a[i][0]);/* write ; */
    Sort(a);
    Print(a); getch();
    x0=0;y0=479;
    for(i=0;i<n;i++)
    {
        if(a[i][1]!=0)
        {
            zuobiao[k].x0=x0;/* 保存坐标 */
            zuobiao[k].y0=y0-a[i][1];
            zuobiao[k].x1=a[i][0];
            zuobiao[k].y1=y0;
            k++;
            printf("Divide the %d Block : %d %d\n ",++num,a[i][1],a[i][0]);
            H=H+a[i][1];
            temp=a[i][1];
            a[i][1]=0;
            x0=a[i][0];
            Divide(x0,y0,W-a[i][0],a,zuobiao,temp);
            y0=479-H;x0=0;
        }
    }
    end = clock();/* 运行后时间点 */
    
    printf("The running time is %lfs\n",(double)(end - start)/CLK_TCK);

    printf("The answer H of %d.txt is : %d \n",n,H);
    printf("Press any key to look the show!");
    getch();
    Show(zuobiao);
    fclose(fp);
    getch();
    closegraph();
}