三角形面积公式的应用

数学公式在acm快速解题中十分重要，掌握规律，熟记公式，可以极大的帮助解题。

三角形有向面积公式：2*s=x0*y1+x1*y2+x2*y0-x0*y2-x1*y0-x2*y1;

当构成三角形的顶点按照逆时针时面积为正，顺时针时为负。

题意：一个矩阵横纵坐标均在1~99之间，每输入一个三角形输出三角形边上和内部共有多少个整点。

解析：核心，判断整点是否在矩形内部

代码如下

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 double gmax(double a,double b,double c)
 5 {
 6     double t;
 7     t=a>b?a:b;
 8     t=t>c?t:c;
 9     return t;
10 }
11 #define eps 1e-9
12 double gmin(double a,double b,double c)
13 {
14     double t;
15     t=a<b?a:b;
16     t=t<c?t:c;
17     return t;
18 }
19 double abs(double a)
20 {
21     if(a<0)return -a;
22     return a;
23 }
24 double gs(double x0,double y0,double x1,double y1,double x2,double y2)
25 {
26     return x0*y1+x1*y2+x2*y0-x0*y2-x1*y0-x2*y1;
27 }
28 int main()
29 {
30     double x0,y0,x1,x2,y1,y2;
31     double s;        int c=0;
32     //cout<<(eps<0.01)<<endl;
33     while(cin>>x0>>y0>>x1>>y1>>x2>>y2)
34     {
35 
36         s=gs(x0,y0,x1,y1,x2,y2);
37         s=abs(s);
38         //cout<<s<<endl;
39         for(int i=(int)gmin(x0,x1,x2);i<=gmax(x0,x1,x2);i++)
40         {
41             for(double k=(int)gmin(y0,y1,y2);k<=gmax(y0,y1,y2);k++)
42             {
43                 if(abs(gs(x0,y0,x1,y1,i,k))+abs(gs(x2,y2,x1,y1,i,k))+abs(gs(x0,y0,x2,y2,i,k))-s<=eps)
44 
45                 {
46                     c++;
47                 }
48             }
49         }
50         cout<<c<<endl;
51         c=0;
52     }
53     return 0;
54 }

View Code

此处应用三角形的面积公式2*s=x0*y1+x1*y2+x2*y0-x0*y2-x1*y0-x2*y1;使得整点的判断十分简单。

除此之外，还有其他应用，如判断一个点在一条直线的上方还是下方

题意：多组输入，第一行两个点的坐标表示一条直线，第二行一个点的坐标，如果点在直线上输出0，如果在直线上方输出1，在直线的下方输出-1；（输入直线不与x轴垂直）

代码如下

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 #define eps 1e-9
 5 double abs(double a)
 6 {
 7     if(a>=0)return a;
 8     return -a;
 9 }
10 double gs(double x0,double y0,double x1,double y1,double x2,double y2)
11 {
12     return x0*y1+x1*y2+x2*y0-x0*y2-x1*y0-x2*y1;
13 }
14 int main()
15 {
16     float x0,y0,x1,y1,x2,y2,s;
17     while(cin>>x0>>y0>>x1>>y1>>x2>>y2)
18     {
19         s=gs(x0,y0,x1,y1,x2,y2);
20         if(abs(s)<=eps)cout<<0<<endl;
21         else if(x0<x1)
22         {
23             if(s>eps)cout<<1<<endl;
24             else cout<<-1<<endl;
25         }
26         else
27         {
28             if(s>eps)cout<<-1<<endl;
29             else cout<<1<<endl;
30         }
31     }
32     return 0;
33 }

View Code