计算几何工具算法-求任意多边形的面积
程序员文章站
2024-03-16 20:28:22
...
题目描述:
给出n边形的n个顶点坐标,求这个n边形的面积
题目分析:
如果在数学上,大概会把这个多边形分成三角形(n-2)个三角形来求
但是这样免不了繁琐的算法,编程复杂度和时间复杂度都很差。
根据矢量叉乘的几何意义 矢量A与矢量B的矢量积是一个矢量,其模等于由A和B作成的平行四边形的面积,下面给出一个公式。
至于证明就不给出了,当个工具用就好,毕竟OI不是数竞.
代码实现:
#include <cstdio>
#include <iostream>
using namespace std;
int n;
struct Point{
double x,y;
Point operator -(Point &s)
{return (Point){x-s.x,y-s.y};}
};
Point d[2005];
double operator *(Point a,Point b)
{
return a.x*b.y-b.x*a.y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&d[i].x,&d[i].y);
double area=0;
for(int i=1;i<=n;i++)
area+=((d[i]*d[i==n?1:i+1])/2.0);
printf("%.2lf",area);
return 0;
}
测试样例:
5
2 1
3 -2
4 2
1 2
2 -1