求任意多边形面积(模板题)
程序员文章站
2024-01-14 19:20:52
...
题目描述
众所周知的是,小X特别喜欢由线条组成的形状,比如说凸多边形,这一天小X正在纸上画着喜欢的凸多边形,这时候小Y走了过来,指着一张图片上的多边形,问小X知道这个图形的面积么,这可把小X难住了,聪明的你一定能够帮助小X解决这个问题,对吧~
输入描述:
多边形上最多有六个点,顺时针or逆时针给定每个点坐标(两个整数表示),保证无多余的点并且没有点重复。
输出描述:
输出一个整数,表示凸多边形的面积,结果四舍五入。
示例1
输入
3
0 0
1 0
2 2
输出
1
示例2
输入
5
-4 -2
1 -3
3 2
-1 4
-4 2
输出
35
题意:求多边形面积。
任意多边形面积叉积公式推导:https://blog.csdn.net/hemmingway/article/details/7814494
还有一种特殊情况的多边形求面积:Pick公式:前提条件(以整点为顶点的任意多边形),它内部整点数为a,它的边上(包括顶点)的整点数为b,则它的面积S = a+b/2-1。证明推导:https://www.cnblogs.com/yujunyong/articles/2010482.html
有前提条件,所以使用有范围限制,但在满足条件时使用比叉积方便。
联想:求所给点顺序为逆时针给出还是顺时针给出:https://blog.csdn.net/Jamence/article/details/77608659
代码如下(模板):
#include <bits/stdc++.h>
using namespace std;
const int maxn=0x3f3f3f;
struct node
{
double x;
double y;
}p[maxn];
int n;
double fun(node a,node b)
{
return a.x*b.y-a.y*b.x;
}
int main()
{
while(scanf("%d", &n)!=EOF&&n!=0)
{
for(int i=0;i<n;i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
double sum=0;
p[n].x=p[0].x;
p[n].y=p[0].y;
for(int i=0;i<n;i++)
{
sum+=fun(p[i],p[i+1]);
}
sum=sum/2.0;
printf("%.1f\n",abs(sum));//面积一定是正数
}
return 0;
}