样例：

输入：

12

3 1

6 3

9 2

8 4

9 6

9 9

8 9

6 5

5 8

4 4

3 5

1 3

12

1000 1000

2000 1000

4000 2000

6000 1000

8000 3000

8000 8000

7000 8000

5000 4000

4000 5000

3000 4000

3000 5000

1000 3000

4

0 0

1000000 0

1000000 1000000

0 1000000

4

0 0

100 0

100 100

0 100

输出：

21

25990001

999998000001

9801

分析：Pick定理：一个计算点阵中顶点在格点上的多边形面积公式：S=a+b/2.0-1，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。

首先利用叉积求多边形的面积S；

然后求出b，方法是枚举每条边，然后以改边构成一个直角三角形，直角边长度是n，m，斜边上有的整数点的个数是gcd（n，m）-1（不包括两端点）最后b=b+n;

即可

最后a=S+1-b/2.0;

需要注意的地方是：a可能爆int

1 #include"stdio.h"  2 #include"string.h"  3 #include"algorithm"  4 #include"stdlib.h"  5 #include"math.h"  6 #include"map"  7 #include"queue"  8 #include"iostream"  9 #define M 1009 10 #define inf 0x3f3f3f3f 11 #define eps 1e-9 12 using namespace std; 13 struct node 14 { 15     double x,y; 16     node(){} 17     node(double x,double y) 18     { 19         this->x=x; 20         this->y=y; 21     } 22     node operator-(node a) 23     { 24         return node(x-a.x,y-a.y); 25     } 26     node operator+(node a) 27     { 28         return node(x+a.x,y+a.y); 29     } 30     double operator*(node a) 31     { 32         return x*a.x+y*a.y; 33     } 34     double operator^(node a) 35     { 36         return x*a.y-y*a.x; 37     } 38 }p[M]; 39 double len(node a) 40 { 41     return sqrt(a*a); 42 } 43 double dis(node a,node b) 44 { 45     return len(b-a); 46 } 47 double cross(node a,node b,node c) 48 { 49     return (b-a)^(c-a); 50 } 51 int gcd(int a,int b) 52 { 53     return b==0?a:gcd(b,a%b); 54 } 55 int point(node a,node b) 56 { 57     int m=(int)(fabs(b.x-a.x)+0.5); 58     int n=(int)(fabs(b.y-a.y)+0.5); 59     int r=gcd(m,n); 60     return r-1; 61 } 62 int main() 63 { 64     int n; 65     while(scanf("%d",&n),n) 66     { 67         for(int i=0;i