求最大圆半径.

HOUSCOUS · 发表于 2004-4-17 13:35:33

其实这道题是可以看成是求最大的正方形.

从资料文件中读取资料:
例如data.txt
4
2左2上2右2下

输出的结果为:
1.0

其中第一行的4表示有4条边, 这4条边从坐标(0, 0)开始, 向左水平位移了2, 然后向上位移2, 再向右位移2, 最后向下位移2. 形成个正方型. 而这个正方形的边长就是一个内切圆能达到的最大的直径.

哪位兄弟用C/C++试试?

xiaocong213 · 发表于 2004-4-17 21:05:22

楼主好像没说清楚爱啊
什么叫有四条边,这四条边的位置怎么样的
按楼主的移法,只要一个点就可以划出一个正方形了爱啊,还用边吗?
而且既然是正方形,只要知道左右移了多少就行了啊,还用上下吗?

HOUSCOUS · 发表于 2004-4-17 22:51:39

也许是我没说清楚吧. 告诉你四条边, 就代表这个图形是个四边形. 至于是怎么连在一起的, 应该说是从坐标轴原点(0, 0)开始, 向左水平位移了2, 然后向上位移2, 再向右位移2, 最后向下位移2. 正好形成个正方型.

我给出的这个例子, 是最简单的情况. 你的程序要从文件中读取资料, 然后进行判断, 我可没说已经告诉你这是个正方形, 而让你求最大的内切圆半径.

例如下面的例子:

10 //代表有十边
10右10上10左10上10右5上30左20下20右5下 // 画边的顺序, 从(0, 0)开始

这就是个不规则图形了吧.

ajinn · 发表于 2004-4-19 22:21:34

这题看着就晕晕

xiaocong213 · 发表于 2004-4-21 18:26:23

#define MAXLINE 256
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
int main(int argc,char **argv)
{
char str[MAXLINE];
int maxofx,maxofy,minofx,minofy;
int i,j,k=0,temp,count;
float l,m,n;
float resultx,resulty;
float r=0;
int zuo,you;
int flag;
int fangxiang;
int bianshu;
FILE *fp;
float tempr;
float tempminr;

      if(argc!=2)
      {
         printf("usage:%s <filename>\n",argv[0]);
      exit(1);
      }

/*打开文件,读取数据*/

if((fp=fopen(argv[1],"r"))==NULL)
{
printf("Error!Can not open file %s\n",argv[1]);
exit(0);
}
if((fgets(str,MAXLINE,fp))==NULL)
{
printf("Error!Read data bianshu error\n");
exit(0);
}
bianshu=atoi(str); /*得出边数*/

int dot[bianshu+1][2];
dot[0][0]=dot[0][1]=0;
i=1;
maxofx=maxofy=minofx=minofy=0;

for(j=0;j<MAXLINE;j++) *(str+j)='\0';
temp=0;
flag=0;
count=0;
for(j=0;j<MAXLINE;j++)
{
if((*(str+j)=fgetc(fp))==EOF)
break;
if((*(str+j)>='0')&&(*(str+j)<='9'))
{
count++;
temp=atoi(str+j-count+1);
continue;
}
else
{
if(flag==1)
{
if(strcmp(str+j-1,"xx")==0)
{
dot[0]=dot[i-1][0];
dot[1]=dot[i-1][1]-temp;
maxofx=dot[0]>maxofx? dot[0]:maxofx;
maxofy=dot[1]>maxofy? dot[1]:maxofy;
minofx=dot[0]<minofx? dot[0]:minofx;
minofy=dot[1]<minofy? dot[1]:minofy;
temp=0;
i++;
flag=0;
count=0;
continue;
}
if(strcmp(str+j-1,"ss")==0)
{
dot[0]=dot[i-1][0];
dot[1]=dot[i-1][1]+temp;
maxofx=dot[0]>maxofx? dot[0]:maxofx;
maxofy=dot[1]>maxofy? dot[1]:maxofy;
minofx=dot[0]<minofx? dot[0]:minofx;
minofy=dot[1]<minofy? dot[1]:minofy;
temp=0;
i++;
flag=0;
count=0;
continue;
}
if(strcmp(str+j-1,"yy")==0)
{
dot[1]=dot[i-1][1];
dot[0]=dot[i-1][0]+temp;
maxofx=dot[0]>maxofx? dot[0]:maxofx;
maxofy=dot[1]>maxofy? dot[1]:maxofy;
minofx=dot[0]<minofx? dot[0]:minofx;
minofy=dot[1]<minofy? dot[1]:minofy;
temp=0;
i++;
flag=0;
count=0;
continue;
}
if(strcmp(str+j-1,"zz")==0)
{
dot[1]=dot[i-1][1];
dot[0]=dot[i-1][0]-temp;
maxofx=dot[0]>maxofx? dot[0]:maxofx;
maxofy=dot[1]>maxofy? dot[1]:maxofy;
minofx=dot[0]<minofx? dot[0]:minofx;
minofy=dot[1]<minofy? dot[1]:minofy;
temp=0;
i++;
flag=0;
count=0;
continue;
}
}
flag=1;
}
}

if((dot[bianshu][0]!=dot[0][0])||(dot[bianshu][1]!=dot[0][1]))
{
printf("所给条件无法组成多边行,请检查是否有误 \n");
exit(0);
}

xiaocong213 · 发表于 2004-4-21 18:28:48

zuo=you=0;
for(i=1;i<bianshu;i++)
{
if(dot[0]==dot[i-1][0])
{
if(dot[1]>dot[i-1][1])
{
if(dot[i+1][0]>dot[0])
you++;
else
zuo++;
}
else
{
if(dot[i+1][0]>dot[0])
                                    zuo++;
                              else
you++;
}
}
else
{
if(dot[0]>dot[i-1][0])
{
if(dot[i+1][1]>dot[1])
zuo++;
else
you++;
}
else
{
if(dot[i+1][1]>dot[1])
you++;
                              else
                                    zuo++;
}
}
}
if(zuo>you)
fangxiang=0;
else
fangxiang=1;
for(l=minofx+0.5;l<maxofx;l+=0.5)
{
for(m=minofy+0.5;m<maxofy;m+=0.5)
{
zuo=0;you=0;
for(i=0;i<bianshu;i++)
{
if(dot[0]==dot[i+1][0])
{
if(l==(float)dot[0])
{
if((m==(float)dot[1])||(m==(float)dot[i+1][1]))
break;
else if((m>(float)dot[1]&&m<(float)dot[i+1][1])||
(m<(float)dot[1]&&m>(float)dot[i+1][1]))
break;
else
continue;
}
else if(l>(float)dot[0])
{
if(dot[i+1][1]>dot[1])
you++;
else
zuo++;
}
else
{
   if(dot[i+1][1]>dot[1])
                                                            zuo++;
                                                      else
you++;
}
}
else
{
if(m==(float)dot[1])
                                             {
                                                      if((l==(float)dot[0])||(l==(float)dot[i+1][0]))
                                                            break;
else if(((m>(float)dot[1])&&m<((float)dot[i+1][1]))||
((m<(float)dot[1])&&(m>(float)dot[i+1][1])))
break;
                                                      else
                                                            continue;
                                             }
                                             if(m>(float)dot[1])
                                             {
                                                      if(dot[i+1][0]>dot[0])
                                                            zuo++;
                                                      else
you++;
                                             }
                                             if(m<(float)dot[1])
                                             {
                                                      if(dot[i+1][0]>dot[0])
you++;
                                                      else
                                                            zuo++;
                                             }
}
}
if( ( (fangxiang==0)&&zuo<you)||( (fangxiang==1)&&zuo>you) )
continue;

xiaocong213 · 发表于 2004-4-21 18:30:23

else
{
tempminr=maxofx-minofx;
for(j=0;j<bianshu;j++)
{
if(dot[j][0]==dot[j+1][0])
{
if(((m>(float)dot[j][1])&&m<((float)dot[j+1][1]))||
((m<(float)dot[j][1])&&(m>(float)dot[j+1][1])))
{
tempr=(float)sqrt((l-dot[j][0])*(l-dot[j][0]));
tempminr=tempr<tempminr? tempr:tempminr;
                                          }
                                          else
                                       {
tempr=(float)sqrt( ((l-dot[j][0])*(l-dot[j][0])+(m-dot[j][1])*(m-dot[j][1]))<((l-dot[j+1][0])*(l-dot[j+1][0])+(m-dot[j+1][1])*(m-dot[j+1][1]))? ((l-dot[j][0])*(l-dot[j][0])+(m-dot[j][1])*(m-dot[j][1]))(l-dot[j+1][0])*(l-dot[j+1][0])+(m-dot[j+1][1])*(m-dot[j+1][1])) );
tempminr=tempr<tempminr? tempr:tempminr;
                                         }
                                    }
                                else
                                {
if(((l>(float)dot[j][0])&&l<((float)dot[j+1][0]))||
                                                ((l<(float)dot[j][0])&&(l>(float)dot[j+1][0])))
                                             {
                                                      tempr=(float)sqrt((m-dot[j][1])*(m-dot[j][1]));
                                                      tempminr=tempr<tempminr? tempr:tempminr;
                                             }
                                             else
                                             {
                                                      tempr=(float)sqrt( ((l-dot[j][0])*(l-dot[j][0])+(m-dot[j][1])*(m-dot[j][1]))<((l-dot[j+1][0])*(l-dot[j+1][0])+(m-dot[j+1][1])*(m-dot[j+1][1]))? ((l-dot[j][0])*(l-dot[j][0])+(m-dot[j][1])*(m-dot[j][1]))(l-dot[j+1][0])*(l-dot[j+1][0])+(m-dot[j+1][1])*(m-dot[j+1][1])) );
                                                      tempminr=tempr<tempminr? tempr:tempminr;
}
}
}
r=tempminr>r? tempminr:r;
}
}
}
printf("r=%f\n",r);
}

xiaocong213 · 发表于 2004-4-21 18:43:02

一次居然贴不完,害得我要贴三次,还有"问号"居然变成了

另外中文的左右上下按两个字节读出来不能判断,因为算法是按两个字节判断的,所以把左改成zz,右改成yy等.大家可以试试能不能进行中文的判断,

xiaocong213 · 发表于 2004-4-21 18:50:24

程序写好后我又发现我的判断还有错误的,主要是在
判断某个点在不在包含的区域
那一段,各位有没有好的想法大家讨论讨论,等我再好好想想

xiaocong213 · 发表于 2004-4-22 11:33:03

现在已经改过了,应该没问题了,大家可以试试.
如果还有问题麻烦贴帖说一下,看看哪里错了再改改

prox2004 · 发表于 2004-4-23 17:31:40

xiaocong213老大,你怎么贴的代码.还有语法错误?
1) for(i=1;i {
2) int dot[bianshu+1][2]; bianshu可是变量啊

另外,简单讲讲主要思路吧.

prox2004 · 发表于 2004-4-23 17:32:11

xiaocong213老大,你怎么贴的代码.还有语法错误?
1) for(i=1;i {
2) int dot[bianshu+1][2]; bianshu可是变量啊

另外,简单讲讲主要思路吧.

prox2004 · 发表于 2004-4-23 18:13:06

int dot[bianshu+1][2]; 这样的用法在g++中是可以.
但应该不符合c++标准.(B.Stroustrup's C++PL SE. sec5.2,P89)
没有必要,最好不要这么用

		自动登录	找回密码
密码			注册

求最大圆半径.

本帖子中包含更多资源