本文目录一览：
求8数码A或A*算法（用C语言）
题目地址:
BFS:
#include iostream
using namespace std;
int fac[10]={1,1};
bool tflag[9];
struct bbit{
unsigned int val:4;
};
struct bbbit
{
unsigned int val:2;
};
struct Node
{
bbit s[9],pos;
int step;
bbbit path[21],tag;
int hashval()
{
int ret=0,i,j,tmp;
memset(tflag,false,sizeof(tflag));
for(i=0;i8;i++)
{
tmp=0;
for(j=0;js[i].val;j++)
if(!tflag[j])
tmp++;
ret+=tmp*fac[8-i];
tflag[s[i].val]=true;
}
return ret;
}
bool up()
{
if(pos.val=2)return false;
s[pos.val].val^=s[pos.val-3].val;
s[pos.val-3].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val-3].val;
path[step].val=0;
pos.val-=3;
return true;
}
bool down()
{
if(pos.val=6)return false;
s[pos.val].val^=s[pos.val+3].val;
s[pos.val+3].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val+3].val;
path[step].val=1;
pos.val+=3;
return true;
}
bool left()
{
if(pos.val==0||pos.val==3||pos.val==6)return false;
s[pos.val].val^=s[pos.val-1].val;
s[pos.val-1].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val-1].val;
path[step].val=2;
pos.val--;
return true;
}
bool right()
{
if(pos.val==2||pos.val==5||pos.val==8)return false;
s[pos.val].val^=s[pos.val+1].val;
s[pos.val+1].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val+1].val;
path[step].val=3;
pos.val++;
return true;
}
bool operator==(const Nodex)const
{
int i;
for(i=0;i9;i++)if(s[i].val!=x.s[i].val)return false;
return true;
}
}Q[362880],S,A,tmp,top;
struct Hash
{
bool d1,d2;
Node D;
}hash[362880];
inline void mkfac(){int i;for(i=2;i=9;i++)fac[i]=fac[i-1]*i;}
inline int eval(char c){return c=='x'?0:c-'0';}
void o(Node x,Node y)
{
int i;
for(i=1;i=x.step;i++)
{
switch(x.path[i].val)
{
case 0:putchar('u');break;
case 1:putchar('d');break;
case 2:putchar('l');break;
case 3:putchar('r');break;
}
}
for(i=y.step;i=1;i--)
switch(y.path[i].val){
case 0:putchar('d');break;
case 1:putchar('u');break;
case 2:putchar('r');break;
case 3:putchar('l');break;
}
puts("");
}
int main()
{
char buf[11];
int i,t,l,r;
bool flag;
mkfac();
while(NULL!=gets(buf))
{
t=0;
for(i=0;i=7;i++)A.s[i].val=i+1;A.s[8].val=0;A.pos.val=8;
for(i=0;buf[i];i++)
{
if(buf[i]==' ')continue;
S.s[t].val=eval(buf[i]);
if(S.s[t].val==0)
S.pos.val=t;
t++;
}
l=r=0;
flag=false;
for(i=0;i362880;i++)hash[i].d1=hash[i].d2=false;
S.step=0;S.tag.val=1;
A.step=0;A.tag.val=2;
Q[r++]=S;//tag.val:1
Q[r++]=A;//tag.val:2
while(l=r)
{
top=Q[l++];
top.step++;
tmp=top;
if(tmp.up())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.down())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.left())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.right())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
}
AA:flag=true;
if(!flag)
puts("unsolvable");
}
return 0;
}
A*:
#include iostream
#include queue
using namespace std;
int fac[10]={1,1};
struct Node
{
int s[9],step,pos;
char path[501];
int hashval()
{
int ret=0,i,j,tmp;
bool flag[9];
memset(flag,false,sizeof(flag));
for(i=0;i8;i++)
{
tmp=0;
for(j=0;js[i];j++)
if(!flag[j])
tmp++;
ret+=tmp*fac[8-i];
flag[s[i]]=true;
}
return ret;
}
bool up()
{
if(pos=2)return false;
s[pos]^=s[pos-3];
s[pos-3]^=s[pos];
s[pos]^=s[pos-3];
path[step]='u';
pos-=3;
return true;
}
bool down()
{
if(pos=6)return false;
s[pos]^=s[pos+3];
s[pos+3]^=s[pos];
s[pos]^=s[pos+3];
path[step]='d';
pos+=3;
return true;
}
bool left()
{
if(pos==0||pos==3||pos==6)return false;
s[pos]^=s[pos-1];
s[pos-1]^=s[pos];
s[pos]^=s[pos-1];
path[step]='l';
pos--;
return true;
}
bool right()
{
if(pos==2||pos==5||pos==8)return false;
s[pos]^=s[pos+1];
s[pos+1]^=s[pos];
s[pos]^=s[pos+1];
path[step]='r';
pos++;
return true;
}
bool operator==(const Nodex)const
{
int i;
for(i=0;i9;i++)if(s[i]!=x.s[i])return false;
return true;
}
void show()
{
int i,j;
for(i=0;i=6;i+=3,coutendl)
for(j=i;j=i+2;j++)
couts[j];
}
bool operator(const Nodex)const
{
int la=0,lb=0,i;
for(i=0;i8;i++)if(s[i]!=i+1)la++;la+=(s[8]!=0);
for(i=0;i8;i++)if(x.s[i]!=i+1)lb++;lb+=(x.s[8]!=0);
return lalb;
}
}S,A,tmp,top;
priority_queueNode Q;
bool hash[362880];
void mkfac(){int i;for(i=2;i=9;i++)fac[i]=fac[i-1]*i;}
int eval(char c){return c=='x'?0:c-'0';}
void output(Node x)
{
int i;
for(i=1;i=x.step;i++)
putchar(x.path[i]);
puts("");
}
int main()
{
char buf[11];
int i,t,l,r;
bool flag;
mkfac();
while(NULL!=gets(buf))
{
t=0;
for(i=0;i=7;i++)A.s[i]=i+1;A.s[8]=0;A.pos=8;
for(i=0;buf[i];i++)
{
if(buf[i]==' ')continue;
S.s[t]=eval(buf[i]);
if(S.s[t]==0)
S.pos=t;
t++;
}
l=r=0;
flag=false;
memset(hash,false,sizeof(hash));
S.step=0;
while(!Q.empty())Q.pop();
Q.push(S);
while(!Q.empty())
{
top=Q.top();
Q.pop();
top.step++;
tmp=top;
if(tmp.up())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.down())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.left())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.right())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
}
AA:flag=true;
if(!flag)
puts("unsolvable");
}
return 0;
}
求一个A*算法的C语言或C++代码，小弟不胜感激，谢谢
1#include iostream
2#include queue
3usingnamespace std;
4
5struct knight{
6int x,y,step;
7int g,h,f;
8booloperator (const knight k) const{ //重载比较运算符
9return f k.f;
10 }
11}k;
12bool visited[8][8]; //已访问标记(关闭列表)
13int x1,y1,x2,y2,ans; //起点(x1,y1),终点(x2,y2),最少移动次数ans
14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8个移动方向
15priority_queueknight que; //最小优先级队列(开启列表)
16
17boolin(const knight a){ //判断knight是否在棋盘内
18if(a.x0|| a.y0|| a.x=8|| a.y=8)
19returnfalse;
20returntrue;
21}
22int Heuristic(const knight a){ //manhattan估价函数
23return (abs(a.x-x2)+abs(a.y-y2))*10;
24}
25void Astar(){ //A*算法
26 knight t,s;
27while(!que.empty()){
28 t=que.top(),que.pop(),visited[t.x][t.y]=true;
29if(t.x==x2 t.y==y2){
30 ans=t.step;
31break;
32 }
33for(int i=0;i8;i++){
34 s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
35if(in(s) !visited[s.x][s.y]){
36 s.g = t.g +23; //23表示根号5乘以10再取其ceil
37 s.h = Heuristic(s);
38 s.f = s.g + s.h;
39 s.step = t.step +1;
40 que.push(s);
41 }
42 }
43 }
44}
45int main(){
46char line[5];
47while(gets(line)){
48 x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
49 memset(visited,false,sizeof(visited));
50 k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
51while(!que.empty()) que.pop();
52 que.push(k);
53 Astar();
54 printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
55 }
56return0;
57}
58
急~关于C语言课程设计用星号构成A~Z字母输出~~~！！！
/* 第一题 */
#include stdio.h
#include string.h
#define SCREEN_COLS 80 /* how many columns does terminal have */
#define HORIZONTAL_DISTANCE 4 /* horizontal distance between two characters (列距) */
#define VERTICAL_DISTANCE 1 /* vertical distance between two rows of characters (行距) */
#define BRUSH_CHAR ('*')
#define BLANK_CHAR (' ')
/* ASCII_TAB字模中字体的高度和宽度 */
#define FONT_ROWS 7
#define FONT_COLS 5
/* 屏幕每行最多可以显示的字符个数 */
#define CHAR_PER_LINE (SCREEN_COLS/(FONT_COLS + HORIZONTAL_DISTANCE))
// ASCII_TAB[] contains all ASCII characters from sp (32) to z (122)
static const unsigned char ASCII_TAB[][5]= //5*7
{
{ 0x00, 0x00, 0x00, 0x00, 0x00 }, // sp
{ 0x00, 0x00, 0x2f, 0x00, 0x00 }, // !
{ 0x00, 0x07, 0x00, 0x07, 0x00 }, // "
{ 0x14, 0x7f, 0x14, 0x7f, 0x14 }, // #
{ 0x24, 0x2a, 0x7f, 0x2a, 0x12 }, // $
{ 0xc4, 0xc8, 0x10, 0x26, 0x46 }, // %
{ 0x36, 0x49, 0x55, 0x22, 0x50 }, //
{ 0x00, 0x05, 0x03, 0x00, 0x00 }, // '
{ 0x00, 0x1c, 0x22, 0x41, 0x00 }, // (
{ 0x00, 0x41, 0x22, 0x1c, 0x00 }, // )
{ 0x14, 0x08, 0x3E, 0x08, 0x14 }, // *
{ 0x08, 0x08, 0x3E, 0x08, 0x08 }, // +
{ 0x00, 0x00, 0x50, 0x30, 0x00 }, // ,
{ 0x10, 0x10, 0x10, 0x10, 0x10 }, // -
{ 0x00, 0x60, 0x60, 0x00, 0x00 }, // .
{ 0x20, 0x10, 0x08, 0x04, 0x02 }, // /
{ 0x3E, 0x51, 0x49, 0x45, 0x3E }, // 0
{ 0x00, 0x42, 0x7F, 0x40, 0x00 }, // 1
{ 0x42, 0x61, 0x51, 0x49, 0x46 }, // 2
{ 0x21, 0x41, 0x45, 0x4B, 0x31 }, // 3
{ 0x18, 0x14, 0x12, 0x7F, 0x10 }, // 4
{ 0x27, 0x45, 0x45, 0x45, 0x39 }, // 5
{ 0x3C, 0x4A, 0x49, 0x49, 0x30 }, // 6
{ 0x01, 0x71, 0x09, 0x05, 0x03 }, // 7
{ 0x36, 0x49, 0x49, 0x49, 0x36 }, // 8
{ 0x06, 0x49, 0x49, 0x29, 0x1E }, // 9
{ 0x00, 0x36, 0x36, 0x00, 0x00 }, // :
{ 0x00, 0x56, 0x36, 0x00, 0x00 }, // ;
{ 0x08, 0x14, 0x22, 0x41, 0x00 }, //
{ 0x14, 0x14, 0x14, 0x14, 0x14 }, // =
{ 0x00, 0x41, 0x22, 0x14, 0x08 }, //
{ 0x02, 0x01, 0x51, 0x09, 0x06 }, // ?
{ 0x32, 0x49, 0x59, 0x51, 0x3E }, // @
{ 0x7E, 0x11, 0x11, 0x11, 0x7E }, // A
{ 0x7F, 0x49, 0x49, 0x49, 0x36 }, // B
{ 0x3E, 0x41, 0x41, 0x41, 0x22 }, // C
{ 0x7F, 0x41, 0x41, 0x22, 0x1C }, // D
{ 0x7F, 0x49, 0x49, 0x49, 0x41 }, // E
{ 0x7F, 0x09, 0x09, 0x09, 0x01 }, // F
{ 0x3E, 0x41, 0x49, 0x49, 0x7A }, // G
{ 0x7F, 0x08, 0x08, 0x08, 0x7F }, // H
{ 0x00, 0x41, 0x7F, 0x41, 0x00 }, // I
{ 0x20, 0x40, 0x41, 0x3F, 0x01 }, // J
{ 0x7F, 0x08, 0x14, 0x22, 0x41 }, // K
{ 0x7F, 0x40, 0x40, 0x40, 0x40 }, // L
{ 0x7F, 0x02, 0x0C, 0x02, 0x7F }, // M
{ 0x7F, 0x04, 0x08, 0x10, 0x7F }, // N
{ 0x3E, 0x41, 0x41, 0x41, 0x3E }, // O
{ 0x7F, 0x09, 0x09, 0x09, 0x06 }, // P
{ 0x3E, 0x41, 0x51, 0x21, 0x5E }, // Q
{ 0x7F, 0x09, 0x19, 0x29, 0x46 }, // R
{ 0x46, 0x49, 0x49, 0x49, 0x31 }, // S
{ 0x01, 0x01, 0x7F, 0x01, 0x01 }, // T
{ 0x3F, 0x40, 0x40, 0x40, 0x3F }, // U
{ 0x1F, 0x20, 0x40, 0x20, 0x1F }, // V
{ 0x3F, 0x40, 0x38, 0x40, 0x3F }, // W
{ 0x63, 0x14, 0x08, 0x14, 0x63 }, // X
{ 0x07, 0x08, 0x70, 0x08, 0x07 }, // Y
{ 0x61, 0x51, 0x49, 0x45, 0x43 }, // Z
{ 0x00, 0x7F, 0x41, 0x41, 0x00 }, // [
{ 0x55, 0x2A, 0x55, 0x2A, 0x55 }, // '\'
{ 0x00, 0x41, 0x41, 0x7F, 0x00 }, // ]
{ 0x04, 0x02, 0x01, 0x02, 0x04 }, // ^
{ 0x40, 0x40, 0x40, 0x40, 0x40 }, // _
{ 0x00, 0x01, 0x02, 0x04, 0x00 }, // '
{ 0x20, 0x54, 0x54, 0x54, 0x78 }, // a
{ 0x7F, 0x48, 0x44, 0x44, 0x38 }, // b
{ 0x38, 0x44, 0x44, 0x44, 0x20 }, // c
{ 0x38, 0x44, 0x44, 0x48, 0x7F }, // d
{ 0x38, 0x54, 0x54, 0x54, 0x18 }, // e
{ 0x08, 0x7E, 0x09, 0x01, 0x02 }, // f
{ 0x0C, 0x52, 0x52, 0x52, 0x3E }, // g
{ 0x7F, 0x08, 0x04, 0x04, 0x78 }, // h
{ 0x00, 0x44, 0x7D, 0x40, 0x00 }, // i
{ 0x20, 0x40, 0x44, 0x3D, 0x00 }, // j
{ 0x7F, 0x10, 0x28, 0x44, 0x00 }, // k
{ 0x00, 0x41, 0x7F, 0x40, 0x00 }, // l
{ 0x7C, 0x04, 0x18, 0x04, 0x78 }, // m
{ 0x7C, 0x08, 0x04, 0x04, 0x78 }, // n
{ 0x38, 0x44, 0x44, 0x44, 0x38 }, // o
{ 0x7C, 0x14, 0x14, 0x14, 0x08 }, // p
{ 0x08, 0x14, 0x14, 0x18, 0x7C }, // q
{ 0x7C, 0x08, 0x04, 0x04, 0x08 }, // r
{ 0x48, 0x54, 0x54, 0x54, 0x20 }, // s
{ 0x04, 0x3F, 0x44, 0x40, 0x20 }, // t
{ 0x3C, 0x40, 0x40, 0x20, 0x7C }, // u
{ 0x1C, 0x20, 0x40, 0x20, 0x1C }, // v
{ 0x3C, 0x40, 0x30, 0x40, 0x3C }, // w
{ 0x44, 0x28, 0x10, 0x28, 0x44 }, // x
{ 0x0C, 0x50, 0x50, 0x50, 0x3C }, // y
{ 0x44, 0x64, 0x54, 0x4C, 0x44 } // z
};
static char get_char_xy(char ch, int x, int y)
{
if (ch ' ' || ch 'z')
ch = ' ';
ch -= ' ';
return (ASCII_TAB[ch][x] (1y)) ? BRUSH_CHAR : BLANK_CHAR;
}
static void print_row(char ch, int row)
{
int i;
for (i = 0; i FONT_COLS; i++) {
printf("%c", get_char_xy(ch, i, row));
}
}
int main(int argc, char *argv[])
{
char str[80] = { '\0' };
int i, j, k, len, index = 0;
printf("Please input a string:\n");
scanf("%s", str);
len = strlen(str);
while (index len) {
for (i = 0; i FONT_ROWS; i++) {
for (j = 0; j CHAR_PER_LINE j + index len; j++) {
print_row(str[index + j], i);
for (k = 0; k HORIZONTAL_DISTANCE; k++) {
printf("%c", BLANK_CHAR);
}
}
printf("\n");
}
index += CHAR_PER_LINE;
for (k = 0; k VERTICAL_DISTANCE; k++) {
printf("\n");
}
}
return 0;
}
/* 第二题 */
#include math.h
#include stdlib.h
#include stdio.h
#include string.h
#define MIN_POINT_NUMBER 3
#define MAX_POINT_NUMBER 100
#define MAX_POINT_COORD 1000.0
typedef struct Point_ {
float x;
float y;
} Point;
typedef struct Circle_ {
Point o; /* centre */
Point p1;
Point p2;
float r; /* radius */
} Circle;
typedef struct {
Point p;
int included;
} Element;
/* return squared distance of points a b */
#define SQUARE(a) ((a)*(a))
#define SQUARED_DISTANCE(a,b) (SQUARE((a).x-(b).x) + SQUARE((a).y-(b).y))
#define DISTANCE(a,b) (sqrt(SQUARED_DISTANCE((a),(b))))
#define MAX(a,b) ((a) (b) ? (a) : (b))
#define MIN(a,b) ((a) (b) ? (a) : (b))
#define EQUAL_FLOAT(a,b) (fabs((a)-(b)) 0.00001)
/* get the circumcircle of a triangle */
static Circle
get_circumcircle(Point a, Point b, Point c)
{
Circle result;
float dx1 = a.x - b.x;
float dx2 = b.x - c.x;
float dy1 = a.y - b.y;
float dy2 = b.y - c.y;
float x1 = (a.x + b.x) / 2.0;
float x2 = (b.x + c.x) / 2.0;
float y1 = (a.y + b.y) / 2.0;
float y2 = (b.y + c.y) / 2.0;
result.o.x = ((dy1*dy2*(y2-y1) + x2*dx2*dy1 - x1*dx1*dy2)) / \
(dx2*dy1 - dx1*dy2);
result.o.y = ((dx1*dx2*(x2-x1) + y2*dy2*dx1 - y1*dy1*dx2)) / \
(dy2*dx1 - dy1*dx2);
result.r = DISTANCE(result.o, a);
result.p1 = a;
result.p2 = c;
return result;
}
/* get the mininal circle that includes three given points
* Note:
* 1) the tree points may be in one line
* or
* 2) the tree points make up a triangle
*/
static Circle
get_min_circle(Point a, Point b, Point c)
{
Circle result;
float ab,bc,ac, max;
ab = DISTANCE(a,b);
bc = DISTANCE(b,c);
ac = DISTANCE(a,c);
max = MAX(ab, MAX(bc,ac));
printf("[%f, %f]\n[%f, %f]\n[%f, %f]\n",a.x,a.y,b.x,b.y,c.x,c.y);
if (EQUAL_FLOAT(max*2, ab+bc+ac)) { /* in the same line */
printf("line\n");
if (EQUAL_FLOAT(max, ab)) {
/* ab is the diameter */
result.o.x = (a.x + b.x) / 2.0;
result.o.y = (a.y + b.y) / 2.0;
result.r = max / 2.0;
result.p1 = a;
result.p2 = b;
} else if (EQUAL_FLOAT(max, bc)) {
/* bc is the diameter */
result.o.x = (b.x + c.x) / 2.0;
result.o.y = (b.y + c.y) / 2.0;
result.r = max / 2.0;
result.p1 = b;
result.p2 = c;
} else {
/* ac is the diameter */
result.o.x = (a.x + c.x) / 2.0;
result.o.y = (a.y + c.y) / 2.0;
result.r = max / 2.0;
result.p1 = a;
result.p2 = c;
}
} else { /* triangle */
/* get the circumcircle of the triangle */
printf("triangle\n");
result = get_circumcircle(a, b, c);
}
printf("The circle's center is [%f, %f], radius is %f\n",
result.o.x, result.o.y, result.r);
return result;
}
int
main(int argc, char *argv[])
{
Circle circle;
Element *elements;
int n = 0, i;
while (n MIN_POINT_NUMBER || n MAX_POINT_NUMBER) {
printf("Please input point number (3-100):\n");
scanf("%d", n);
}
elements = (Element*)malloc(sizeof(Element)*n);
memset(elements, 0, sizeof(Element)*n);
for (i = 0; i n; i++) {
printf("Please input point (%d in %d):\n", i+1, n);
scanf("%f %f", elements[i].p.x, elements[i].p.y);
}
elements[0].included = 1;
elements[1].included = 1;
elements[2].included = 1;
circle = get_min_circle(elements[0].p, elements[1].p, elements[2].p);
for (i = 0; i n; i++) {
if (elements[i].included)
continue;
if (DISTANCE(elements[i].p, circle.o) - circle.r 0.00001) {
circle = get_min_circle(circle.p1, circle.p2, elements[i].p);
}
elements[i].included = 1;
}
return 0;
}
