newplan

阿基米德在洗澡時發現浮力原理,高興得來不及穿㆖褲子,跑到街㆖大喊:Eureka(我找到了)。
posts - 39, comments - 26, trackbacks - 0, articles - 4
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

算法实验三(集装箱)

Posted on 2008-06-05 09:05 山泉弯延 阅读(398) 评论(0)  编辑 收藏 引用
/*
08.6.2
*/

/*------------------INCLUDES BEGIN---------------*/
#include 
<cstdlib>
#include 
<iostream>
#include 
<fstream>
#include 
<string>
#include 
<cmath>
#include 
<algorithm>
#include 
<QApplication>
#include 
<QWidget>
#include 
<QPainter>
#include 
<Qt>
/*-------------------INCLUDES END----------------*/


/*-------------------MACROS BEGIN----------------*/
#define INPUTFILE  
"./c30.txt"
#define MAX        
100000
#define PI         
3.141592653589793238462643383279
#define 
ERROR      1e-7
#define BUFFER     
100
#define RANG_LOW   
0 
#define RANG_UP    
6283
/*-------------------MACROS END------------------*/


/*-----------NAMESPACE STD DECLARE BEGIN---------*/
using std::cin;
using std::ifstream;
using std::ios;
using std::cout;
using std::endl;
using std::sort;
using std::
string;
/*----------NAMESPACE STD DECLARE  END------------*/



/*-------------CLASS CIRCLE BEGIN-----------------*/
class circle{
      
public:
      
double r;
      
double x;
      
double y;  
      bool   v;  
};
/*-------------CLASS CIRCLE END-------------------*/


/*-------------CLASS GREEDY BEGIN-----------------*/
    
/*THE MOST IMPORTANT CLASS IN THIS PROGRAM*/
class Greedy
{
public:
        Greedy(void);
        ~Greedy(){};
        void GreedyCPU(void);
//THE MAIN METHOD IN THIS CLASS
        void AvailRate(void); 
//CACULATE THE AVAILEBAL  RATE
        circle c[BUFFER];   
//CIRCLE BUFFER 
        
int getN(){return N;}
        
double getW(){return W;}
        
double getH(){return H;} 
        
double getP(){return p;}
 
 
private
        friend bool mycmp(circle t1,circle t2); 
        bool CanBeInput(
int which);//JUDGE CAN C[WHICH] BE PUT INTO THE CHEST
        ifstream  Fin;      
//INPUT DATA   
        
int N;              //CIRCLE NUMBER
        
double W;           //CHEST WIDTH
        
double H;           //CHEST HIGHT
        
double L;           //CHEST LONG 
        
double s;           //CHEST AREA
        
double sc;          //CIRCLE TOTAL AREA
        
double p;           //AVAILE RATE
        
int    k;           //CAN PUTED CIRCLE NUM
        
int t;              //FROM C[T] THAT CAN BE PUT INTO THE CHEST   
}; 
/*GREEDY METHEDS*/ 
/*===================================================*/
bool mycmp(circle t1,circle t2) 
{
     return t1.r
>t2.r;

/*===================================================*/ 
Greedy::Greedy()
{
    Fin.open(INPUTFILE,ios::in);
    Fin
>>N;
    Fin
>>W;
    Fin
>>H;
    Fin
>>L; 
    
for(int i=0;i<N;i++)
    {
      Fin
>>c[i].r;
      c[i].v
= false;
    }
    sort(c,c
+N,mycmp);
    t
=-1
    s
=W*H;
    sc
=0;
    k
=0;
           
}
/*===================================================*/
bool Greedy::CanBeInput(
int which)
{   
  
if(c[which].x+c[which].r>W+ERROR||c[which].y+c[which].r>H+ERROR
     ||c[which].x
-c[which].r+ERROR < 0||c[which].y-c[which].r+ERROR < 0)
  return 
false;
  
for(int i=t;i<which;i++)//将 i=0 改为 i=t; 
  
if(c[i].v==true)
  {
   
double t1=c[which].x-c[i].x;
   
double t2=c[which].y-c[i].y;
   
double d =sqrt(t1*t1+t2*t2);
   
if( c[which].r+c[i].r> d+ERROR  )
    return  
false;             
  }    
  return 
true;
}
/*===================================================*/
void Greedy::GreedyCPU(void)      
{
  bool   boo
=false;
  
double tempX=MAX;
  
double tempY=MAX;
  
double minX=MAX;
  
double minY=MAX;   
  
for(int i=0;i<N;i++)
      
if(c[i].r*2+ERROR <&& c[i].r*2+ERROR<H)
      {
      c[i].x
=c[i].r;
      c[i].y
=c[i].r;
      c[i].v
=true;
      t
=i;
      break;               
      } 
  
if(t==-1)
    {cout
<<"null circle can be inputed"<<endl;return;}

  
for(int i=t+1;i<N;i++)
  { 
    
for(int m=t;m<i;m++)
    {   
if(c[m].v==true){
         
for(int k=RANG_LOW;k<RANG_UP;k++)      
         { 
           c[i].x
=c[m].x+(c[i].r+c[m].r)*cos(double(k)/1000);
           c[i].y
=c[m].y+(c[i].r+c[m].r)*sin(double(k)/1000);
         
           
if(CanBeInput(i))
           {
            
             boo
=true;
             
if(minX>c[i].x)
              {minX
=c[i].x;tempY=c[i].y;}
             
if(minY>c[i].y)
              {minY
=c[i].y;tempX=c[i].x;}                 
           }
//if
         }
//for
    
        
if(boo)
        {
         
if(minX<minY){c[i].x = minX;c[i].y = tempY;} 
         
else {c[i].x = tempX; c[i].y = minY;} 
        
         c[i].v
=true;
         minX
=MAX;
         minY
=MAX;
         boo
=false;
         break;          
        }
//if boo
      }
//if (c[m].v==true)
    }
//for m
  } 
//for  i  
}
/*===================================================*/  
void Greedy::AvailRate()
{
   
for(int i=0;i<N;i++)
    
if(c[i].v==true)
      {k
++;
       sc
+=c[i].r*c[i].r*PI;
      }
  p
=sc/s;
}
/*===================================================*/     

/*--------------CLASS GREEDY END-------------------*/

/*--------------CLASS NEWBOX BEGIN-----------------*/

class NEWBOX:
public QWidget
{   
    
public:
        NEWBOX(QWidget 
*parent=0);
        
    protected:
        void paintEvent(QPaintEvent 
*event); 
    
private:
        Greedy g;
};
/*===================================================*/ 
NEWBOX::NEWBOX(QWidget 
*parent):QWidget(parent)
{
     setFixedSize(g.getW()
*50,g.getH()*50);
     g.GreedyCPU();
     g.AvailRate(); 
     char temp[
5];
     sprintf(temp,
"%f",g.getP());
     char title[
30]="using:";
     strcat(title,temp);
     setWindowTitle(title);
     setPalette(QPalette(QColor(
250250200)));
     setAutoFillBackground(
true);
     
}
/*===================================================*/ 
void NEWBOX::paintEvent(QPaintEvent 
*)
{    QPainter painter(this);
     painter.setPen(Qt::SolidLine);
     painter.setBrush(Qt::blue);
     painter.translate(
0,0);
     
int num=g.getN();
     
for(int i=0;i<num;i++)
        
if(g.c[i].v==true){
            float x 
= (float)g.c[i].x*50;
            float y 
= (float)g.c[i].y*50;
            float r 
= (float)g.c[i].r*50;
            painter.drawEllipse(QRectF(x
-r,g.getH()*50-y-r,2*r,2*r));
        }
}
/*===================================================*/ 




/*--------------CLASS NEWBOX END------------------*/



/*--------------------MAIN BEGIN-------------------*/
int main(int argc, char *argv[])
{   
    
    QApplication app(argc, argv);
    NEWBOX   newbox;
    newbox.show();
    return app.exec();
}
/*--------------------MAIN END--------------------*/

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理