果园里的树（判断点是否在三角形内）

2019-11-08 00:42:46

字体：大中小

来源：转载

供稿：网友

果园里的树排列成矩阵。它们的x和y的坐标都是1~99的整数。输入若干个三角形，依次统计每个三角形内部和边界上共有多少棵树。

分析： 1.对于每个点，判断是否在三角形内。假设三角形ABC，判断点O，则O在三角形ABC的内部或者边界上当且仅当Sabc=Soab+Sobc+Soca。 2.判断两个浮点数a和b是否相等时，尽量判断fabs(a-b)是否小于一个事先给定的eps，如1e-9。 3.可以用海伦公式S=√(p(p-a)(p-b)(p-c))a(其中半周长p=(a+b+c)/2),使用时要小心浮点数误差。 4.area2()得到的是三角形(x0,y0)-(x1,y1)-(x2,ye)的有向面积的两倍。

这里写图片描述

#include<iostream>using namespace std;double area2(double x0,double y0,double x1,double y1,double x2,double y2){ return abs(x0*y1+x2*y0+x1*y2-x2*y1-x0*y2-x1*y0);}int main(){ double x0,y0,x1,y1,x2,y2; const double eps=1e-9; while(cin>>x0>>y0>>x1>>y1>>x2>>y2){ double area=area2(x0,y0,x1,y1,x2,y2); int count=0; for(int i=1;i<=99;i++) for(int j=1;j<=99;j++){ double a1,a2,a3; a1=area2(i,j,x0,y0,x1,y1); a2=area2(i,j,x0,y0,x2,y2); a3=area2(i,j,x1,y1,x2,y2); if(fabs(a1+a2+a3-area)<eps) count++; } cout << count << endl; } return 0;}

上一篇：土地问题（求出土地被分成多少面，有知识点）

下一篇：【优雅编程之道】之异常的6点建议