PolygonArea

题目描述

莫卡想请你帮她计算一个包含 nn 个点的简单多边形面积。

输入

第一行包含一个正整数 nn，代表点数。

接下来n行，每行两个整数 xi,yix_i,y_i，代表点的坐标，点的坐标按照逆时针顺序给出。

3≤n≤1000,0≤∣xi∣,∣yi∣≤1063≤n≤1000,0≤|x_i|,|y_i|≤10^6。

输出

输出一个正整数，代表简单多边形面积的两倍。

输入样例

1
2
3
4
5
4
25 25
40 40
10 20
40 0

输出样例

1
600

鞋带公式

S=12∣∑i=1nxi∗(yi+1−yi−1)∣=12∣∑i=1nyi∗(xi+1−xi−1)∣S=\frac{1}{2}|\sum_{i=1}^{n}x_i*(y_{i+1}-y_{i-1})|=\frac{1}{2}|\sum_{i=1}^{n}y_i*(x_{i+1}-x_{i-1})|

设xix_i下标从1到nn，则x0=xnx_0=x_n，xn+1=x1x_{n+1}=x_1。yiy_i同理。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll DoubleArea(vector<ll> x, vector<ll> y, int n)
{
    x[0] = x[n];
    x[n + 1] = x[1];
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = ans + y[i] * (x[i + 1] - x[i - 1]);
    }
    return ans > 0 ? ans : -1 * ans;
}
int main()
{
    int n;
    cin >> n;
    vector<ll> x(1010);
    vector<ll> y(1010);
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
    }

    cout << DoubleArea(x, y, n);
    return 0;
}