大意略。
思路:通过叉积可以算出多边形的有向面积(就算是凹变形也没关系),这样,我们根据移动方向把所有的点存起来,然后算通过多边形面积公式算出结果即可。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; typedef __int64 LL; struct Point { int x, y; Point(int x = 0, int y = 0) : x(x), y(y) { } bool operator < (const Point& a) const { if(a.x != x) return x < a.x; return y < a.y; } }; typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); } int Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } LL PolygonArea2(Point *p, int n) { LL area = 0; for(int i = 1; i < n-1; i++) area += (LL)Cross(p[i]-p[0], p[i+1]-p[0]); return area > 0? area : -area; } Point read_point() { Point A; scanf("%d%d", &A.x, &A.y); return A; } const int maxn = 1000010; const int dx[] = {0, 1, 1, 1, 0, 0, 0, -1, -1, -1}; const int dy[] = {0, -1, 0, 1, -1, 0, 1, -1, 0, 1}; int n, len; Point P[maxn]; char dir[maxn]; int pc; void init() { pc = 1; } int idx(char c) { return c - '0'; } void read_case() { init(); P[0] = Point(0, 0); scanf("%s", dir+1); len = strlen(dir+1); for(int i = 1; i <= len; i++) { P[pc++] = Point(P[i-1].x+dx[idx(dir[i])], P[i-1].y+dy[idx(dir[i])]); } } void solve() { read_case(); LL ans = PolygonArea2(P, pc); if(pc & 1) printf("%I64d.5\n", ans/2); else printf("%I64d\n", ans/2); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }