题目地址：POJ 1265
题意：给定一个格点多边形，求出内部点数in，边上点数on，和面积S。
思路：运用的定理很多。
1.皮克定理：S=in+on/2-1，即in=(2*S+2-on)/2。
2.多边形的面积公式：按顺序求相邻两个点与原点组成的向量的叉积之和。
3.求边上的格点数：以格子点为顶点的线段，覆盖的点的个数为GCD(dx,dy)，其中，dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0，则覆盖的点数为dy或dx。
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <sstream>#include <algorithm>#include <set>#include <queue>#include <stack>#include <map>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;int gcd(int a,int b){ while(b){ int r=b; b=a%b; a=r; } return a;}int area(int x1,int y1,int x2,香蕉大神){ return x1*y2-x2*y1;}int main(){ int T,n,i; int dx,dy; int x1,y1,x2,y2; int icase=1; int in,on; double S; scanf("%d",&T); while(T--){ scanf("%d",&n); x1=y1=x2=y2=0; in=on=S=0; while(n--){ scanf("%d %d",&dx,&dy); x2=x1+dx;//有两个点组成的矩形的点 y2=y1+dy; S+=area(x1,y1,x2,y2); on+=gcd(abs(dx),abs(dy)); x1=x2; y1=y2; } in=(S+2-on)/2; printf("Scenario #%d:n",icase++); printf("%d %d %.1lfnn",in,on,S/2.0); } return 0;}