POJ 1654 Area(计算几何）

本文主要是介绍POJ 1654 Area(计算几何），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算一个多边形的面积

把多边形划分成多个三角形，利用叉积计算有向面积累加即可

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;typedef long long ll;struct Point {ll x, y;Point() {}Point(ll x, ll y) {this->x = x;this->y = y;}
};typedef Point Vector;ll Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;} //叉积Vector operator + (Vector A, Vector B) {return Vector(A.x + B.x, A.y + B.y);
}Vector operator - (Vector A, Vector B) {return Vector(A.x - B.x, A.y - B.y);
}//n边形的面积
ll PolygonArea(Point *p, int n) {double area = 0;for (int i = 1; i < n - 1; i++)area += Cross(p[i] - p[0], p[i + 1] - p[0]);if (area < 0) area = -area;return area;
}const int N = 1000005;
const int d[10][2] = {0, 0, 1, -1, 1, 0, 1, 1, 0, -1, 0, 0, 0, 1, -1, -1, -1, 0, -1, 1};
Point p[2], O;
int t, n;
char str[N];int main() {scanf("%d", &t);while (t--) {scanf("%s", str);n = 1;int now = 0, pre = 1;p[now] = Point(0, 0);ll ans = 0;O.x = 0; O.y = 0;while (str[n - 1]) {swap(pre, now);p[now].x = p[pre].x + d[str[n - 1] - '0'][0];p[now].y = p[pre].y + d[str[n - 1] - '0'][1];n++;if (n == 1) continue;ans += Cross(p[pre] - O, p[now] - O);}if (ans < 0) ans = -ans;if (ans % 2) printf("%lld.5\n", ans / 2);else printf("%lld\n", ans / 2);}return 0;
}

这篇关于POJ 1654 Area(计算几何）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---