algorithm - 给定边长的网格多边形面积

Question

输入:

包含 32 位整数的长度为 N(N <= 10000)的表 T。每个整数表示正方形网格上多边形连续边的长度和方向(每个顶点都有整数坐标)。如果整数为正数，则表示边缘向上或向右。如果整数为负，则边缘向下或向左。边垂直于它的邻居。边既不相交也不重叠。顶点不相互重叠。

示例输入 T:

2, -3, -1, 1, -1, 2

代表两个多边形(我们选择哪个并不重要):

箭头表示第一条边对应T中的前2个。

输出:

整数表示给定多边形的表面积。对于示例性输入，输出应为 5。

期望的时间复杂度:O(N)
所需的内存复杂度(不计算输入):O(1)

您能介绍一下这样的算法及其背后的原理吗？

Answer 1

算法:

int area(int[] T) {
    int area = 0;
    int x = 0;
    for (int i = 0; i < T.length; i += 2) {
        x += t[i];
        area += x * t[i + 1];
    }
    return Math.abs(area);
}

描述:

我们的多边形封闭在一个大矩形中。基于此，我们正在计算构建形状的小矩形的面积 - 多边形内部的矩形以及外部的矩形(符号相反)。

我们从多边形的哪个顶点开始并不重要。一开始我们需要一个基线，我们将从中计算垂直(也可以是水平的，没关系)顶点的平移。我们得到第一个数字 - 它会告诉我们，我们的第一个顶点从基线移动了多少。第二个数字是根据第二个坐标的平移。通过将这对相乘，我们得到了总和中的第一个矩形。

第二个矩形由第三点和第四点描述:

• 加上第一个数的第三个数是顶点的垂直平移

• 第四个数字是顶点的水平平移。将这些点相乘得到第二个矩形。

我们将继续对表中的其余数字执行此操作。我们正在添加矩形区域。结果是总和的绝对值。