POJ 1654. 面积计算题解

1. 题意理解

你会得到多组测试数据，每组数据是一个由数字组成的字符串（长度≤$1e6$）。字符串中数字 $1-9$ 代表移动方向（$5$ 为结束符），按顺序移动将形成闭合多边形（起点为原点，最终回到原点）。需计算该多边形的面积，输出格式为：若面积为整数则直接输出，否则输出整数部分加 $.5$（如 $0.5$、$3.5$）。

2. 思路分析

（1）方向与坐标映射

每个数字 $1-9$ 对应平面中的移动方向，需预先定义 坐标增量表：

• 数字 $d$ → 增量 $(dx[d], dy[d])$，例如：
  • $6$（东）→ $(1, 0)$，$8$（北）→ $(0, 1)$，$9$（东北）→ $(1, 1)$；
  • $2$（南）→ $(0, -1)$，$4$（西）→ $(-1, 0)$，$7$（西北）→ $(-1, 1)$ 等。

（2）鞋带公式（高斯面积公式）

多边形面积可通过顶点坐标的 叉积和 计算：
[ \text{面积} = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right| ]
其中 $(x_i, y_i)$ 是第 $i$ 个顶点坐标，$(x_{n+1}, y_{n+1}) = (x_1, y_1)$（闭合多边形）。

（3）坐标追踪与叉积累加

从原点 $(0, 0)$ 出发，逐字符解析移动方向，计算 每一步的顶点坐标，并累加叉积项 $x_i y_{i+1} - x_{i+1} y_i$。遍历结束后，利用公式计算面积。

3. 具体实现步骤

步骤一：构建方向映射表

定义数组 $dx$ 和 $dy$，索引对应数字 $0-9$（$0$ 未使用），存储各方向的坐标增量：

int dx[] = {0, 1, 1, 1, 0, 0, 0, -1, -1, -1}; // 数字1-9的x增量
int dy[] = {0, -1, 0, 1, -1, 0, 1, -1, 0, 1}; // 数字1-9的y增量

步骤二：处理输入与特判

• 读取测试用例数 $t$，逐组处理字符串 $s$。
• 若字符串以 $5$ 开头，或长度 $<3$（无法形成有效多边形），直接输出 $0$。

步骤三：计算顶点坐标与叉积和

• 初始化起点 $(x=0, y=0)$，叉积和 $area=0$。
• 遍历字符串（除最后一个字符 $5$）：
  • 提取当前数字 $d = s[i] - '0'$，计算下一个顶点 $(nx, ny) = (x+dx[d], y+dy[d])$。
  • 累加叉积项 $area += x*ny - y*nx$，更新当前坐标 $x=nx, y=ny$。

步骤四：计算并输出面积

• 叉积和取绝对值：$area = abs(area)$。
• 面积为 $area / 2$，若 $area$ 为奇数，输出需补 $.5$（如 $area=3$ → 面积 $1.5$）。

4. 复杂度分析

• 时间复杂度：

  • 每组用例遍历字符串一次，时间为 $O(n)$（$n$ 为字符串长度）。
  • 总时间复杂度为 $O(T*n)$（$T$ 为测试用例数），可处理 $n≤1e6$ 的规模。

• 空间复杂度：

  • 仅需存储字符串和常数级变量（坐标、叉积和等），空间复杂度为 $O(1)$（忽略输入存储）。

标程（代码）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

// 方向映射：dx[d], dy[d] 对应数字d的坐标增量（d=1~9）
int dx[] = {0, 1, 1, 1, 0, 0, 0, -1, -1, -1};
int dy[] = {0, -1, 0, 1, -1, 0, 1, -1, 0, 1};
const int N = 1000000 + 5;
char s[N];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);
        int len = strlen(s);
        if (s[0] == '5' || len < 3) { // 特判：无效输入
            printf("0\n");
            continue;
        }

        LL area = 0;
        LL x = 0, y = 0; // 当前顶点坐标
        for (int i = 0; i < len - 1; ++i) { // 遍历到倒数第二个字符（跳过最后的5）
            int d = s[i] - '0';
            LL nx = x + dx[d];
            LL ny = y + dy[d];
            area += x * ny - y * nx; // 累加叉积项
            x = nx;
            y = ny;
        }

        area = abs(area); // 叉积和取绝对值
        printf("%lld", area / 2);
        if (area % 2) { // 奇数时补.5
            printf(".5");
        }
        printf("\n");
    }
    return 0;
}

关键细节说明

1. 方向映射表：需确保 $dx$ 和 $dy$ 与数字的方向完全对应（如 $7$ 对应西北，$dx[7]=-1$，$dy[7]=1$），否则坐标计算错误。
2. 叉积累加：每一步的叉积项 $x*ny - y*nx$ 直接反映相邻顶点的几何贡献，累加后取绝对值即可得到面积的两倍。