poj1265 -- Area（皮克定理）

题目链接http://poj.org/problem?id1265题目大意一个机器人每次给出移动的dx和dy然后让你求出这个多边形的边经过的整点数和包围的点数还有这个多边形的面积。解题思路1对于一条直线上的整点坐标数量为gcdx2-x1, y2-y12多边形面积求法就是找一个源点求所有与源点相连的两个点的向量积的和然后除以2就是多边形了面积了。3皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式该公式可以表示为2S2ab-2其中a表示多边形内部的点数b表示多边形边界上的点数S表示多边形的面积。所以如果我们求内部点的数量的话将公式转换一下就行了。实现代码#include iostream #include cmath using namespace std; const int MAX_N 200; struct Node { double x, y; }; struct Node p[MAX_N]; int gcd(int a, int b) { if (b 0) { return a; } else { return gcd(b, a%b); } } double slove(struct Node x, struct Node y) { return x.x*y.y - x.y*y.x; } int main() { ios::sync_with_stdio(false); int t; cin t; for (int q1; qt; q) { int n; int ans 0; double area 0; int point_num 0; cin n; for (int i1; in; i) { int dx, dy; cin dx dy; p[i].x p[i-1].xdx; p[i].y p[i-1].ydy; ansgcd(abs(dx), abs(dy)); areaslove(p[i], p[i-1]); } area/2; if (area0) { area fabs(area); } point_num int(area 1 - ans/2.0); printf(Scenario #%d:\n%d %d %0.1lf\n, q, point_num, ans, area); printf(\n); } return 0; }