题目地址：POJ 1265
题意：给定一个格点多边形，求出内部点数in，边上点数on，和面积S。
思路：运用的定理很多。
1.皮克定理：S=in+on/2-1，即in=2*S+2-on)/2。
2.多边形的面积公式：按顺序求相邻两个点与原点组成的向量的叉积之和。
3.求边上的格点数：以格子点为顶点的线段，覆盖的点的个数为GCDdx,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 gcdint a,int b){ whileb){ int r=b; b=a%b; a=r; } return a;}int areaint 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); whileT–){ scanf”%d”,&n); x1=y1=x2=y2=0; in=on=S=0; whilen–){ scanf”%d %d”,&dx,&dy); x2=x1+dx;//有两个点组成的矩形的点 y2=y1+dy; S+=areax1,y1,x2,y2); on+=gcdabsdx),absdy)); x1=x2; y1=y2; } in=S+2-on)/2; printf”Scenario #%d:\n”,icase++); printf”%d %d %.1lf\n\n”,in,on,S/2.0); } return 0;}