目录

• 题目
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例
    • 输入
    • 输出
• 解析
  • 向量的向量积
  • 再来看这道题
• 代码

题目

题目描述

给出一个简单多边形(没有缺口)，它的边要么是垂直的，要么是水平的。要求计算多边形的面积。
多边形被放置在一个X−Y的笛卡尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数(因此多边形的面积也为整数)。

输入格式

第一行给出多边形的顶点数n(n≤100)。接下来的几行每行给出多边形一个顶点的坐标值X和Y(都为整数并且用空格隔开)。顶点按逆时针方向逐个给出。并且多边形的每一个顶点的坐标值−200≤x,y≤200。多边形最后是靠从最后一个顶点到第一个顶点画一条边来封闭的。

输出格式

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

输入输出样例

输入

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

输出

9

解析

向量的向量积

这道题涉及了一个非常有趣的东西：向量的向量积（叉乘）

\[|\overrightarrow{a} \times \overrightarrow{b}| = |\overrightarrow{a}| · |\overrightarrow{b}| · \sin \theta \]

来看看，这个式子是不是似曾相识？没错，这个和我们利用正弦定理搞出的三角形面积十分像：

\[S = 1/2 · a · b ·\sin \theta \]

那么这个就有一个应用了：求三角形面积
响亮的向量积坐标表示为：

\[| \overrightarrow{a} \times \overrightarrow{b} | = x1 · y2 - x2 · y1 \]

利用这个就可以在平面直角坐标系中轻松地算出三角形面积

再来看这道题

很显然，只需要把多边形分成好多三角形然后计算即可

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k;
int a[1000001];
int dp[10001][10001];
inline ll Read() {
    ll ans = 0;
    char Ch = getchar() , Las = ' ';
    while(!isdigit(Ch)) {Las = Ch;Ch = getchar();}
    while(isdigit(Ch)) {ans = (ans << 3) + (ans << 1) + Ch - '0';Ch = getchar();}
    if(Las == '-') ans = -ans;
    return ans;
}

inline void Write(ll x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) Write(x / 10);
    putchar(x % 10 + '0');
}

int x[100001],y[1000001];
int s = 0;

int main() {
    n = Read();
    for(int i = 1;i <= n; i++) {
	    x[i] = Read();
	    y[i] = Read();
    }    	
    x[n + 1] = x[1];
    y[n + 1] = y[1];
    for(int i = 1;i <= n; i++) {
	    s += x[i] * y[i + 1] - x[i + 1] * y[i];
    }
    Write(abs(s / 2));
    return 0;
}