C程序问题

Question

输入N个点的坐标，判断这N个点能否构成一个凸多边形
程序：#include<iostream.h>
//#define N
const int N=4;
int tt(double p[][2],int a,int b) //a为下标，不能为float
{
int temp[N],k=0;
double t;
for(int i=0;i<N;i++)
{
if(i==a||i==b)
{
continue;
}
t=p[i][0]*(p[b][1]-p[a][1])+(p[a][0]-p[b][0])*p[i][1]-p[a][0]*p[b][1]+p[b][0]*p[a][1];
if(t==0)
return 0;
else
if(t>0)
temp[k++]=1;
else
temp[k++]=-1;
}
for(int j=1;j<k;j++)
{
if(temp[0]!=temp[j]) return 0;
}
return 1;
}
int real(double p[][2])
{
int flag[N],m=0;
for(int i=0;i<N;i++)
{
flag[i]=0;
}
for( i=0;i<N;i++)
{
for(int j=1;j<N;j++)
{
if(flag[j]) continue;
if(tt(p,m,j))
{
flag[m]=1;
m=j;
break;
}
}
}
flag[m]=1;
for(i=0;i<N;i++)
{
if(flag[i]==0)
return 0;
}
if(tt(p,0,m)) return 1;
return 0;
}
void main()
{
double p[N][2];
char ch='y';
while (ch=='y'||ch=='Y')
{
cout<<"请输入这N个点坐标:"<<endl;
for(int i=0;i<N;i++)
{
cout<<" 第"<<i<<"个点坐标:";
cin>>p[i][0]>>p[i][1];
//cin>>**p>>*(*p+1);
cout<<p[i][0]<<","<<p[i][1]<<endl;
}
if (real(p))
cout<<"能";
else
cout<<"不能";
cout<<endl<<"是否继续判断?(继续请输入y&Y)";
cin>>ch;
}
}
你的农夫过河问题解释的真的很详细，所以想拜托你再帮着看看这个问题，给一下详细的解释。另外，如果把这个程序改成C语言的，怎么改？谢谢了

Answer 1

先简单的说一下思路，用反证法的思想，什么情况下无法构成凸多边形？
答案是，对于任意一点a, 如果找不到这样的一点b, 就无法构成凸多边形。什么样的b呢？
除a, b以外，其它所有点都在过a, b的直线ab的一侧。
如果对于任意一点a，总能找到这样的b，使所有其它点都位于ab的一侧，那么这些点就能构成凸多边形。

这样说起来很绕人，最好的办法就是自己画一画。
先画一个凸多边形，然后任找一点，你会发现这个点和其它点做的直线中，总是有这样两条(而且只有两条)直线 —— 除直线外的点都在这条直线的一侧。
再画一个凹多边形，然后找到那个“凹”的点，这个点无论与其它哪个点连一直线，直线外的点总是在两侧都有。

在程序中，判断点是不是在一侧的方法是用直线方程，原始的样子是这样的：
(y - ya) / (x - xa) = (yb - ya) / (xb - xa)
这个就是高中是学过的两点式。
对公式进行转换：
=> (y - ya) * (xb - xa) - (x - xa) * (yb - ya) = 0
=> x * (yb - ya) + y * (xa - xb) - xa * yb + xb * ya = 0

对应的是程序中的：
t=p[i][0]*(p[b][1]-p[a][1]) + p[i][1]*(p[a][0]-p[b][0]) - p[a][0]*p[b][1]+p[b][0]*p[a][1];
其中
p[i][0] = x
p[i][1] = y
p[a][0] = xa
p[a][1] = ya
p[b][0] = xb
p[b][1] = yb
当x, y在直线ab上时，x * (yb - ya) + y * (xa - xb) - xa * yb + xb * ya为0，如果在ab的两侧，公式的结果一个大于0，一个小于0。具体情况和ab的情况有关，这儿只要知道不一样就可以了。
函数tt判断对于直线ab，是否直线外的点都在其同一侧。
for(i=0; i<N; i++)
{
if(i==a || i==b)
continue;
t=p[i][0]*(p[b][1]-p[a][1]) + p[i][1]*(p[a][0]-p[b][0]) - p[a][0]*p[b][1]+p[b][0]*p[a][1];
if(t==0)
return 0;
else
if(t>0)
temp[k++]=1;
else
temp[k++]=-1;
}
就是用来计算a, b两个点和直线外的点关系的。temp记录点和直线的关系，这里有个特殊情况，就是有三点共线的情况，再这个程序当中，一旦有3点共线，立即判定不可能线外直线在同一侧。
所以t = 0时，直接返回0
for(j=1;j<k;j++)
{
if(temp[0]!=temp[j]) return 0;
}
判定所有点是否在同一侧，如果有一个点不在，返回0

real函数查找所有的点，看对于每一个点，是否能找到使所有直线外点都在同一侧直线。
flag记录一个点是否能找到上面说的这种直线，如果能，为1，否则为0。
for(i=0;i<N;i++)
{
flag[i]=0;
}
初始化记录。
for( i=0;i<N;i++)
{
for( j=1;j<N;j++)
{
if(flag[j]) continue;
if(tt(p,m,j))
{
flag[m]=1;
m=j;
break;
}
}
}
flag[m]=1;
这个循环i=0;i<N;i++将在循环体内遍历每一个点，本来可以用tt(p, i, j)来判定点i是否能找到点j，满足所有线外点在一侧的条件。
可能原来写程序的人觉得当找到点m和点j满足条件时，用另一个点j作为下一个搜索的点会更有效率，所以采取了这种方案。
这个具体的哪个好一点，我没细想过，反正都可以实现。

for(i=0;i<N;i++)
{
if(flag[i]==0)
return 0;
}

只要有一个点不满足条件(flag[i] == 0)就不可能构成凸多边形，返回0。

后面是输入和输出，没什么好讲的。

把C++改成C语言的没有一个同样的办法，只能是针对具体的程序。
具体操作，说起来比较罗嗦，我已经帮你改完了，你自己对照着看就明白了。

#include <stdio.h>

#define N 4
int tt(double p[][2], int a, int b)
{
int temp[N], k = 0;
double t;
int i, j;

for(i=0; i<N; i++)
{
if(i==a || i==b)
continue;
t=p[i][0]*(p[b][1]-p[a][1]) + p[i][1]*(p[a][0]-p[b][0]) - p[a][0]*p[b][1]+p[b][0]*p[a][1];
if(t==0)
return 0;
else
if(t>0)
temp[k++]=1;
else
temp[k++]=-1;
}
for(j=1;j<k;j++)
{
if(temp[0]!=temp[j]) return 0;
}
return 1;
}
int real(double p[][2])
{
int flag[N],m=0, i, j;
for(i=0;i<N;i++)
{
flag[i]=0;
}
for(i=0;i<N;i++)
{
for(j=1;j<N;j++)
{
if(flag[j]) continue;
if(tt(p,m,j))
{
flag[m]=1;
m=j;
break;
}
}
}
flag[m]=1;
for(i=0;i<N;i++)
{
if(flag[i]==0)
return 0;
}
if(tt(p,0,m)) return 1;
return 0;
}
int main()
{
double p[N][2];
char ch='y';
int i;

while (ch=='y'||ch=='Y')
{
printf("请输入这N(N=%d)个点坐标:\n", N);
for(i=0;i<N;i++)
{
printf("第%d个点坐标:", i);
scanf("%lf%lf", &p[i][0], &p[i][1]);
printf("%f, %f\n", p[i][0], p[i][1]);
}
if (real(p))
printf("能");
else
printf("不能");
printf("\n是否继续判断?(继续请输入 y | Y)");
fflush(stdin);
scanf("%c", &ch);
}
return 0;
}

这个相关的东西我不是太孰，如果有什么没说到的地方，可以具体的再问一下，我再补充。来自：求助得到的回答

Answer 2

把头文件改下,再把输入输出改下就可以了,不好意思我用手机给你会答的改起来很麻烦.Cin改成Csanf,Cout改成Printf,具体怎样你按相关写法改就行了 本回答被网友采纳

Answer 3

大概写了下，代码给你参考。
程序很简单，就是数组下标的问题需要注意下。

在VC++6.0 和 g++编译器编译环境中均验证通过。
#include<stdio.h>

int main()
{
/*统计结果表示*/
char* stars[10] = {"*",
"**",
"***",
"****",
"*****",
"******",
"*******",
"********",
"*********",
"**********"};
/*投票*/
int grade[] = {3,4,2,5,6,7,8,5,2,2,
1,3,5,6,7,8,9,10,2,2,
3,4,5,6,7,8,9,10,8,7,
6,5,4,5,6,7,8,7,6,5};
/*投票结果*/
int result[10];
for(int i = 0; i < 10; i++)
{
result[i] = 0;
}

for(int i = 0; i < 40; i++)
{
result[grade[i]-1]++;
}

printf("grade\tCount Histogram \n");
for(int i = 0; i < 10; i++)
{
if( result[i] == 0 ) continue;
printf( "%d\t%s\n", i+1, stars[ result[i]-1 ] );
}
}

运行结果：
grade Count Histogram
1 *
2 *****
3 ***
4 ***
5 *******
6 ******
7 ******
8 *****
9 **
10 **