果园里的树

2019-11-11 01:57:26

字体：大中小

来源：转载

供稿：网友

记录下来题目及代码算是学习的过程以后方面查阅题目介绍：果园里的树排列成矩阵。他们的x和y的坐标均是1~99的整数。输入若干个三角形，依次统计每个三角形内部和边界上共有多少棵树。输入： 1.5 1.5 1.5 6.8 6.8 1.5 10.7 6.9 8.5 1.5 14.5 1.5

输出： 15

17 此题用三角形有向面积来解，求有向面积2倍的函数为：

double area(double x0,double y0,double x1,double y1,double x2,double,y2) { return x0*y1+x2*y0+x1*y2-x0*y2-x1*y0-x2*y1; }

若求其面积，即没有方向的：则为fabs(S)/2; 可以用行列式来记住这个式子：

　　|x0 y0 1| 2S=|x1 y1 1|=x0*y1+x2*y0+x1*y2-x2*y1-x0*y2-x1*y0; 　　|x2 y2 1|

若三角形三个点按逆时针排列，则有向面积为正，否则为负。

#include<iostream>#include<math.h>using namespace std;double squre(double x0,double y0,double x1,double y1,double x2,double y2){ return (x0*y1+x2*y0+x1*y2-x2*y1-x0*y2-x1*y0);}int main(void){ double x0,x1,x2,y0,y2,y1,x,y; while(cin>>x0>>y0>>x1>>y1>>x2>>y2){ int temp=0; for(int i=1;i<100;++i) for(int j=1;j<100;++j){ x=i*1.0,y=j*1.0; double s1,s2,s3,s; s1=fabs(squre(x,y,x1,y1,x2,y2)); s2=fabs(squre(x,y,x2,y2,x0,y0)); s3=fabs(squre(x,y,x0,y0,x1,y1)); s=fabs(squre(x0,y0,x1,y1,x2,y2)); if(fabs(s-s1-s2-s3)<=1e-9) temp++; } cout<<temp<<endl; }}

ps:再附上海伦公式s=sqrt(p*(p-a)(p-b)(p-c));其中p=(a+b+c)/2;注：尽量少用海伦公式存在小数点误差，慎用…

上一篇：测试下

下一篇：Swift3按顺序只取前五个最高分组成排行榜，sorted array of top 5 scores leaderboard