这是热身赛的一道签到题,写博客的目的主要是熟悉一下向量点叉积的写法。

(叉积求多边形面积:hdu2036,模版题)

题目:


解题思路:


四边形面积公式:(也适用于凹四边形)

s=(m*n*sinA)/2;  其中m,n是对角线的长度,A是对角线的夹角,可以通过向量点积之后求得sinA

叉积:(适用于凹凸多四边形)其中cross代表叉积

叉积之后的结果是个向量,但是我们需要用的是它对应的标量,两个向量的叉积值是它们组成的三角形的有向面积(有正负之分,如图)的二倍。

叉积值的公式:

也可以写成a.x*b.y-a.y*b.x;

对于n多边形,我们可以把它分成n-2三角形来求面积,而三角形的面积可以用两个向量叉积的一半来求,如果是凸多边形,向量叉积的结果都是正的(三角形的有向面积),对于凹多边形,有些划分三角形的方法出现叉积结果是负的情况,正好这些负值可以抵消掉正值中多算的部分,所以这个方法对于所有的多边形都适用。

ac代码:


(只放叉积的代码,虽然没有测评,但是目测能过)

#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define maxn 106
typedef long long ll;
using namespace std;
struct node{
    double x,y;
    node(double x=0,double y=0):x(x),y(y){}//构造函数
}a[maxn];
node operator - (node a,node b)
{
    return node(a.x-b.x,a.y-b.y);
}
ll t;
double cross(node a,node b)
{
    return a.x*b.y-a.y*b.x;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        double ans=0;
        for(int i=0;i<4;i++)
            cin>>a[i].x>>a[i].y;
        for(int i=1;i<=2;i++)
            ans+=cross(a[i]-a[0],a[i+1]-a[0]);
        printf("%.1lf\n",ans/2);
    }
}