#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <time.h>
#include "graphics.h"


#define PI 3.1415926   

double *x,*y,*r;  //保存圓柱體半徑
double W,H,L;//W為集裝箱的寬度,H為集裝箱的高度，L為集裝箱的長度也是圓柱形木材的長度
int n,*flag,first,m=0;
//n為圓柱形木材的個數(shù),數(shù)組flag標記來判斷是否已放入集裝箱，fisrt為第一個可以放置,m為放入的個數(shù)

struct Coordinate
{//保存坐標,和半徑
    double x0,y0;
    double r0;
};

struct Coordinate Round[40];

void BubbleSort()
{//冒泡排序,半徑從大到小排序
    int i,j;
    double temp;
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            if(r[i]<r[j])
            {
                temp=r[i];
                r[i]=r[j];
                r[j]=temp;
            }
}

void Greedy(double x0,double y0,double r0)
{
    int i,j;
    double angle;


    Round[m].x0=x0;
    Round[m].y0=y0;
    Round[m].r0=r0;
    m++;
    //保存坐標位置
    for(i=first;i<n;i++)    
    { /*尋找未放入的木材i */
        if(!flag[i])
        {
            for(angle=-PI/2;angle<=3*PI/2;angle+=0.001)  
            {/*在木材周圍尋找可以放入木材i的位置*/
                x[i]=x0+(r0+r[i])*cos(angle);
                y[i]=y0+(r0+r[i])*sin(angle);
                flag[i]=1;
                if(x[i]-r[i]<0||x[i]+r[i]>W||y[i]-r[i]<0||y[i]+r[i]>H)
                {//判斷是否超出邊界,是則取回圓柱體.
                    x[i]=0;
                    y[i]=0;
                    flag[i]=0;
                    continue;
                }
                for(j=first;j<n;j++)   /*判斷是否和已經(jīng)放入的木材重疊*/
                    if(flag[j]&&j!=i)
                	{
                        if(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)<pow(r[i]+r[j],2))
                        {//重疊則取回圓柱.
                            x[i]=0;
                            y[i]=0;
                            flag[i]=0;
                            break;
                    	}
                	}
                if(flag[i]) break;
            }
            if(flag[i]) Greedy(x[i],y[i],r[i]);//從新放入的圓柱體開始遞歸
        }
    }
        
}


void Print()
{
    int i;
    for(i=0;i<n;i++)
        printf("%lf  %lf  %lf\n",x[i],y[i],r[i]);
}


void Show ()
{/*圖形界面顯示函數(shù)*/
     int gdriver,gmode,i,j;
     detectgraph(&gdriver,&gmode);
     initgraph(&gdriver, &gmode, "");
     setbkcolor(BLUE);
     setfillstyle(1,WHITE);
     setcolor(WHITE);
     bar(0,0,W*10,H*10);
     for(i=0;i<m;i++)
     {
         j=i+1;
         j=j%8; /* 文件顏色 */
         setfillstyle(1,j);
         setcolor(j);
         getch();
         circle(Round[i].x0*10,Round[i].y0*10,Round[i].r0*10);
     }
}




void main()
{
    int i,gdriver,gmode;
    double area=0;
    FILE *fp;
    clock_t start,end;
    start = clock();/* 開始時時間點 */
    
    if((fp=fopen("c17.txt","rw"))==NULL)/* read .txt */
    {
        printf("Cannot open infile\n");
        return;
    }
    fscanf(fp,"%d %lf %lf %lf",&n,&W,&H,&L);
    r=(double *)malloc(n*sizeof(double));
    x=(double *)malloc(n*sizeof(double));
    y=(double *)malloc(n*sizeof(double));
    flag=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        fscanf(fp,"%lf",&r[i]);
        x[i]=0;
        y[i]=0;
        flag[i]=0;
    }

    BubbleSort();
    //Print() ;
    for(i=0;i<n;i++)    /*尋找第一個可以放入容器的木材*/
    {
        if( 2*r[i]<=W && 2*r[i]<=H )
        { 
            first=i;
            flag[i]=1;
            x[i]=r[i];
            y[i]=r[i];
            Greedy(x[i],y[i],r[i]);
            break;
        }
    }
    for(i=0;i<n;i++)
    {
        if(flag[i])
        {
            printf("%lf  %lf  %lf\n",x[i],y[i],r[i]);
            area+=PI*r[i]*r[i];
        }
    }

    printf("The input number is %d \n",m);
    printf("The using percentage of container: %lf\n",area/W/H);
    end = clock();/* 運行后時間點 */
    
    printf("The running time is %lfs\n",(double)(end - start)/CLK_TCK);
    printf("Press any key to look the show!");
    getch();

    Show();
    closegraph();
    fclose(fp);
}