P2785

Point_Nine · 2021-07-12 07:12:34 · 题解

P2785

前置知识

计算几何基础公式：向量叉乘，两点距离公式。

向量叉乘：模长等于两个向量围成平行四边形面积，实际上是计算三维向量（本题只使用本公式计算面积）。

代码片段：

double vec_ch(node a1,node a2)
{
       return a1.x*a2.y-a2.x*a1.y;
}

两点距离公式：用勾股定理求解，x轴距离平方与y轴距离平方开根号。

代码片段：

double dis(node a,node b)
{
    return sqrt(pow(b.y-a.y,2)+pow(b.x-a.x,2));
}

基本思想：求得四边形面积，然后乘磁通量求解。

分情况讨论：

凸多边形。

要求凸多边形面积，仅需以一个端点开始，将n边形分割为（n-2）个三角形，用向量叉乘求面积，累加面积。

凹多边形

类似凸多边形，现将编号以此排序然后，一条一条边枚举，如果逆时针转就面积加，逆时针就减去该面积，容斥之后为凹边形面积，不过无需另外计算旋转方向，因为叉乘时已经计算方向，直接累加即可。

面积累加代码实现：

double ans=0;
    for(int i=3;i<=n;i++)
    {
        cin>>p[i].x>>p[i].y;
        line[i-1].x=p[i].x-p[1].x;
        line[i-1].y=p[i].y-p[1].y;
        ans+=vec_ch(line[i-1],line[i-2])/2;
    }

tips:叉乘求得面积是向量围成平行四边形面积，所以面积除以二才为三角形面积。

完整代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
       double x,y;
}p[110000],s[110000],line[110000];
void swap(node &a,node &b)
{
     node mid;
     mid=a;
     a=b;
     b=mid;
}
double vec_ch(node a1,node a2)
{
       //printf("%.3lf\n",a1.x*a2.y-a2.x*a1.y);
       return a1.x*a2.y-a2.x*a1.y;
}
double dis(node a,node b)
{
    return sqrt(pow(b.y-a.y,2)+pow(b.x-a.x,2));
}
int main()
{
    int n;
    double m;
    cin>>n>>m;
    cin>>p[1].x>>p[1].y;
    cin>>p[2].x>>p[2].y;
    line[1].x=p[2].x-p[1].x;
    line[1].y=p[2].y-p[1].y;
    double ans=0;
    for(int i=3;i<=n;i++)
    {
        cin>>p[i].x>>p[i].y;
        line[i-1].x=p[i].x-p[1].x;
        line[i-1].y=p[i].y-p[1].y;
        ans+=vec_ch(line[i-1],line[i-2])/2;
    }
    printf("%.4lf",abs(ans)*m);
}