自动搬运

查看原文

来自洛谷，原作者为

	Point_Nine **

搬运于2025-08-24 21:41:36，当前版本为作者最后更新于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);
}