Posted on 2008-06-05 09:05
山泉弯延 阅读(528)
评论(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 <W && 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(250, 250, 200)));
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--------------------*/