本文主要是介绍POJ 1265 Area(PICK定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
PICK定理：平面上以格子点为顶点的简单多边形的面积=边上的点数/2+内部的点数+1
那么只需要计算出面积和边上点的个数， 就能求出内部点的个数了
面积利用三角剖分即可，边上的点的个数为所有线段加起来，每条线段为dx，dy的GCD
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;struct Point {int x, y;Point() {}Point(int x, int y) {this->x = x;this->y = y;}void read() {scanf("%d%d", &x, &y);}
};typedef Point Vector;int 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边形的面积
int PolygonArea(Point *p, int n) {int 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;
}int gcd(int a, int b) {if (!b) return a;return gcd(b, a % b);
}int cal(Point a, Point b) {int dx = a.x - b.x;if (dx < 0) dx = -dx;int dy = a.y - b.y;if (dy < 0) dy = -dy;return gcd(dx, dy);
}const int N = 105;int t, n;Point p[N];int main() {int cas = 0;scanf("%d", &t);while (t--) {scanf("%d", &n);p[0].x = p[0].y = 0;n++;int x, y;for (int i = 1; i < n; i++) {scanf("%d%d", &x, &y);p[i].x = p[i - 1].x + x;p[i].y = p[i - 1].y + y;}int d = cal(p[n - 1], p[0]);for (int i = 1; i < n; i++)d += cal(p[i - 1], p[i]);int a = PolygonArea(p, n);printf("Scenario #%d:\n", ++cas);printf("%d %d %.1f\n\n", (a - d + 2) / 2, d, a * 1.0 / 2);}return 0;
}
这篇关于POJ 1265 Area(PICK定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
