P1183 多边形的面积【洛谷算法习题】

P1183 多边形的面积

网页链接

P1183 多边形的面积

题目描述

给出一个没有缺口的简单多边形，它的边是垂直或者水平的，要求计算多边形的面积。

多边形被放置在一个x O y xOyxOy的笛卡尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数，因此多边形的面积也为整数。

注意：可能存在连续的三个顶点在一条直线上的情况。

输入格式

第一行给出多边形的顶点数n nn。

接下来n nn行，每行给出多边形一个顶点的坐标值x xx和y yy，用空格隔开。

顶点按逆时针方向逐个给出。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。

输出格式

一行，一个整数，表示多边形的面积。

输入输出样例 #1

输入 #1

10 0 0 4 0 4 1 3 1 3 3 2 3 2 2 1 2 1 3 0 3

输出 #1

9

说明/提示

对于100 % 100\%100%的数据，1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100，− 200 ≤ x , y ≤ 200 -200 \le x,y \le 200−200≤x,y≤200。

解题思路

本题核心是鞋带公式求解简单多边形面积，适配题目中水平/垂直边、逆时针顶点的条件。鞋带公式是计算任意简单多边形面积的通用方法：将所有顶点按顺序存储，最后把终点与起点闭合，遍历计算每一组相邻顶点的叉乘和x i y i + 1 − x i + 1 y i x_i y_{i+1} - x_{i+1} y_ixi​yi+1​−xi+1​yi​，将总和取绝对值后除以2，即为多边形面积。题目明确面积为整数，直接取整输出即可。该公式自动忽略连续共线顶点，无需额外处理，计算过程仅需线性遍历顶点，时间复杂度O ( n ) O(n)O(n)，简洁高效且精准。

总结

核心逻辑：使用鞋带公式，通过顶点坐标叉乘和计算多边形面积。
关键操作：闭合顶点序列、累加叉乘项、取绝对值减半后取整。
效率保障：线性遍历计算，公式简洁，自动处理共线顶点，适配题目数据范围。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;doublea[105][2];doubleans=0;intmain(){ll n;cin>>n;for(ll i=0;i<n;i++)cin>>a[i][0]>>a[i][1];a[n][0]=a[0][0],a[n][1]=a[0][1];for(ll i=0;i<n;i++)ans+=0.5*(a[i][0]*a[i+1][1]-a[i][1]*a[i+1][0]);ll a=ans;cout<<a<<endl;return0;}