题目链接：
http://poj.org/problem?id=1265
题目大意：
一个机器人每次给出移动的dx和dy，然后让你求出这个多边形的边经过的整点数和包围的点数，还有这个多边形的面积。
解题思路：
1，对于一条直线上的整点坐标数量为gcd（x2-x1, y2-y1）
2，多边形面积求法就是找一个源点，求所有与源点相连的两个点的向量积的和，然后除以2就是多边形了面积了。
3，皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-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 q=1; q<=t; q++) { int n; int ans = 0; double area = 0; int point_num = 0; cin >> n; for (int i=1; i<=n; i++) { int dx, dy; cin >> dx >> dy; p[i].x = p[i-1].x+dx; p[i].y = p[i-1].y+dy; ans+=gcd(abs(dx), abs(dy)); area+=slove(p[i], p[i-1]); } area/=2; if (area<0) { 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; }
