C语言 输出结果不对（统计三角形区域内多少棵树问题）

Question

果园里的数 xy坐标为1到99的整数，输入一个三角形的坐标 统计内部和边界有多少棵树 样例输入1.5 1.5 1.5 6.8 6.8 1.5 样例输出15
以下是通过有向面积编写的程序 哪里错了 为何输出30
#include
double area2(double x0,double y0,double x1,double y1,double x2,double y2)
{
return x0*y1+x1*y2+x2*y0-x2*y1-x0*y2-x1*y0;
}
int main()
{
double x0,x1,x2,y0,y1,y2,i,j;
int count=0;
scanf("%lf %lf %lf %lf %lf %lf",&x0,&y0,&x1,&y1,&x2,&y2);
for(i=1;i<100;i++)
for(j=1;j<100;j++)
{
if(area2(x0,y0,x1,y1,x2,y2)==(area2(i,j,x0,y0,x1,y1)+area2(i,j,x1,y1,x2,y2)+area2(i,j,x2,y2,x0,y0)))
count++;
}
printf("%d",count);
return 0;
}

Answer 1

该回答引用ChatGPT

该程序存在以下问题：

• 代码中的算法使用了点是否在三角形内的判断方法，但使用的是浮点数计算，存在精度问题，可能会导致判断错误。

• 程序使用了两层嵌套的循环来遍历整个坐标系，但这样的复杂度为 O(n^2)，当数据规模很大时，程序的运行时间会非常长。

• 对于每个坐标点，都会调用 area2 函数三次来计算点与三角形三个顶点所构成的三个三角形的面积，这会浪费计算资源。

• 在判断点是否在三角形内的时候，对于点在三角形的边界上的情况没有特判，导致边界上的点没有被正确统计。

修改建议：

• 可以使用更为稳定和准确的方法来判断点是否在三角形内，例如射线法和叉积法等。其中，叉积法相对简单，可以通过判断点与三角形的三条边所构成的向量叉积是否同号来判断点是否在三角形内。

• 为了避免使用两层嵌套循环，可以使用一个单层循环遍历整个坐标系，并在循环中判断每个点是否在三角形内。

• 为了减少重复计算，可以将三角形的面积计算结果保存下来，在后续的判断中直接使用。

• 需要特判边界上的点，可以将叉积结果为0的点（即点在三角形的某条边上）加入到统计结果中。