| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 761 人关注过本帖
标题:求能够包含随机产生的点的边数最少的凸多边形
只看楼主 加入收藏
liulanggood
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2007-3-22
收藏
 问题点数:0 回复次数:0 
求能够包含随机产生的点的边数最少的凸多边形

各位大虾,帮忙看看这个程序有什么错误好吗??????
#include "stdio.h"
#include "math.h"
#include "time.h"
#include "dos.h"

#define N 100
#define M 10
#define P 10

typedef float F;
typedef struct
{F x;
F y;
int n;
}DT;
typedef struct
{F z;
F m;
}AT;

int suiji()
{long int i,a;
struct time t;
gettime(&t);
a=t.ti_hour*1000000+t.ti_min*10000+t.ti_sec*100+t.ti_hund;
i=a%N;
return(i);
}

F jiefc(F x1,F y1,F x2,F y2,F x)
{F y;
y=abs(((y2-y1)/(x2-x1))*(x-x1));
return(y);
}

F tn(F x1,F y1,F x2,F y2)
{F n;
n=abs((y1-y2)/(x1-x2));
return(n);
}

main()
{int i,j,k,q,f,b1,n,n2,t1,t2,p1,p2,n1,q1,f1;
static int e[4];
F x2,y2,p3,p4,t;
DT b[4][N],a[N];
AT g,x[4],y[4];
struct wo
{F s;
int p;
} d[4][N];

n=suiji()%P+1;
for(i=0;i<n;i++)
{t1=suiji();
t2=suiji();
p3=(F)(t1)/M;
p4=(F)(t2)/M;
a[i].x=p3;
a[i].y=p4;
a[i].n=i+1;
}

for(i=0;i<n-1;i++)
{if(a[i].x>a[i+1].x) x[0].z=x[1].z=a[i+1].x;
if(a[i].x<a[i+1].x) x[2].z=x[3].z=a[i+1].x;
if(a[i].y>a[i+1].y) y[0].m=x[1].m=a[i+1].y;
if(a[i].y<a[i+1].y) y[2].m=x[3].m=a[i+1].y;
}

for(j=0;j<4;j++)
{q=0; b1=1; p2=0;
for(i=0;i<n;i++)
{t=jiefc(x[b1].z,x[b1].m,y[p2].z,y[p2].m,a[i].x);
if(j==0||j==2)
if(a[i].y>t)
{b[j][q].x=a[i].x;
b[j][q].y=a[i].y;
b[j][q].n=a[i].n;
q+=1;
e[j]+=1;
}
if(j==1||j==3)
if(a[i].y<t)
{b[j][q].x=a[i].x;
b[j][q].y=a[i].y;
b[j][q].n=a[i].n;
q+=1;
e[j]+=1;
}
}
b1+=1;
p2+=1;
if(b1==4) b1=1;
}
for(i=0;i<4;i++)
for(k=0;k<e[i];k++)
for(j=0;j<e[i]-k;j++)
{if(i==0||i==3)
{if(b[i][j].x<b[i][j+1].x)
{x2=b[i][j].x; y2=b[i][j].y; n2=b[i][j].n;
b[i][j].x=b[i][j+1].x; b[i][j].y=b[i][j+1].y;
b[i][j+1].x=x2; b[i][j+1].y=y2;
b[i][j].n=b[i][j+1].n; b[i][j+1].n=n2;
}
}
if(i==1||i==2)
if(b[i][j].x>b[i][j+1].x)
{x2=b[i][j].x; y2=b[i][j].y; n2=b[i][j].n;
b[i][j].x=b[i][j+1].x; b[i][j].y=b[i][j+1].y;
b[i][j+1].x=x2; b[i][j+1].y=y2;
b[i][j].n=b[i][j+1].n; b[i][j+1].n=n2;
}
}

for(i=0;i<4;i++)
{g.z=y[3-i].z; g.m=y[3-i].m;
p1=0; n1=0; q1=0;
while(1)
{f1=0;
for(j=p1;j<e[i];j++)
{d[i][q1].s=tn(g.z,g.m,b[i][j].x,b[i][j].y);
d[i][q1].p=j+1; q1+=1; f1+=1;
}
n1+=1;
for(k=(e[i]-f1);k<e[i];k++)
if(d[i][k].s>d[i][k+1].s)
f=d[i][k+1].p-1;
printf("%5d",b[i][f].n);
t=e[i]-f; q1=n1;
g.z=b[i][f].x; g.m=b[i][f].y;
if(t==0) break;
}
}
}

搜索更多相关主题的帖子: 多边形 随机 
2007-04-15 18:55
快速回复:求能够包含随机产生的点的边数最少的凸多边形
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022471 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved