c语言 输入n个点的坐标 求能组成多少个三角形 用结构体解答。。

Answer 1

/*
三角形的生成过程，一条线段和不与该线段共线的一点可构成一个三角形，平面内n个点，每个点作为起始端点与其他n-1个点各
可连成n-1条线段，组成的线段跟不属于该线段的点判断是否共线，如果共线则不会生成三角形，否则则构成三角形。

注意：此程序中没有对是否有重合点进行判断，可以添加此功能。还有就是本程序的点坐标假设都是整型变量
*/

/*http://zhidao.baidu.com/question/396020525.html?fr=uc_push&push=core&oldq=1&group=1*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct _Point
{
int x; //x坐标值
int y; //y坐标值
}POINT, * pPoint;

pPoint setPt(int n); //要求用户输入三角形的坐标信息
void showCoorInfo(pPoint pt, int n); //显示各个点的坐标信息
int getNumofTan(pPoint pt, int n); //获取可以组成的多边形的个数
bool isLine(POINT pt1, POINT pt2, POINT pt3); //判断三点是否为共线

int main(void)
{
int n, num;
printf("Pls enter the num of pt:\n");
scanf("%d", &n);

pPoint pt = setPt(n);

num = getNumofTan(pt, n);
printf("您输入的坐标为：\n");

showCoorInfo(pt, n);

printf("\n共可以组成 %d 个三角形.\n", num);

return 0;
}

pPoint setPt(int n)
{
int i;
pPoint pt;
pt = (pPoint)malloc(sizeof(POINT)*n);
if(NULL==pt)
{
printf("Failed mem located!\n");
exit(-1);
}

printf("Now enter your coor, like 20 50\n");
for(i=0; i<n; i++)
{
printf("The %dth coor:\n", i+1);
scanf("%d %d", &(pt+i)->x, &(pt+i)->y);
}

return pt;
}

void showCoorInfo(pPoint pt, int n)
{
int i;
for(i=0; i<n; i++)
{
if(i>0 && i%5==0)
printf("\n");
printf("(%4d, %4d)\t", (pt+i)->x, (pt+i)->y);
}
printf("\n");

return ;
}

int getNumofTan(pPoint pt, int n)
{
int num = 0;
int i, j, k;
for(i=0; i<n-2; i++) //因为i标识的是线段的首点， 所以最大i是第n-2个点
{
for(j=i+1; j<n-1; j++) //j标识的是线段的尾点， 所以最大j是第n-1个点
{
//构成pt[i]--pt[j]的线段，由于j是从i+1开始的，所以没有重复线段
for(k=j+1; k<n; k++)//k可以一直循环到n
{
if(!isLine(*(pt+i), *(pt+j), *(pt+k)))
num++;
}
}
}

return num;
}

bool isLine(POINT pt1, POINT pt2, POINT pt3)
{
int dx1, dy1, dx2, dy2;
dy1 = pt2.y - pt1.y;
dx1 = pt2.x - pt1.x;
dy2 = pt3.y - pt2.y;
dx2 = pt3.x - pt2.x;

if(dy1*dx2 == dy2*dx1)
return true;
else
return false;

}

/*
IDE: VC 6.0 运行结果

Pls enter the num of pt:
5
Now enter your coor, like 20 50
The 1th coor:
0 0
The 2th coor:
100 0
The 3th coor:
100 100
The 4th coor:
200 50
The 5th coor:
100 0
您输入的坐标为：
( 0, 0) ( 100, 0) ( 100, 100) ( 200, 50) ( 100, 0)

共可以组成 10 个三角形.
Press any key to continue

这是另一组数据的测试效果
Pls enter the num of pt:
5
Now enter your coor, like 20 50
The 1th coor:
0 0
The 2th coor:
0 100
The 3th coor:
0 200
The 4th coor:
100 100
The 5th coor:
100 0
您输入的坐标为：
( 0, 0) ( 0, 100) ( 0, 200) ( 100, 100) ( 100, 0)

共可以组成 9 个三角形.
Press any key to continue
*/