poj 2954 Triangle Pick 定理

题目描述: http://poj.org/problem?id=2954

题目大意: 给定顶点都是整数的三角形, 试求出该三角形内部的整点个数(不包括边界).

首先简要描述一下Pick 定理:
    给定顶点坐标均是整点（或正方形格点）的简单多边形， Pick 定理说明了其面积S和内部格点数目i、边上格点数目b 的关系：
　　S = i + b/2 - 1。
　　(其中i 表示多边形内部的点数,b 表示多边形边界上的点数,S 表示多边形的面积)
   
    Pick 定理在百度百科:http://baike.baidu.com/view/3207200.html

    直接浙大模板之

#include <cstdio>

#define abs(x) ((x)>0?(x):-(x))
struct point {
    int x,y;
};

int gcd(int a,int b) {
    return b?gcd(b,a%b):a;
}

//多边形上的网格点个数
int grid_onedge(int n,point* p) {
    int i,ret=0;
    for (i=0; i<n; i++)
        ret+=gcd(abs(p[i].x-p[(i+1)%n].x),abs(p[i].y-p[(i+1)%n].y));
    return ret;
}

//多边形内的网格点个数
int grid_inside(int n,point* p) {
    int i,ret=0;
    for (i=0; i<n; i++)
        ret+=p[(i+1)%n].y*(p[i].x-p[(i+2)%n].x);
    return (abs(ret)-grid_onedge(n,p))/2+1;
}

int main() {
    point t[3];
	while(scanf("%d %d %d %d %d %d", &t[0].x, &t[0].y,
			    &t[1].x, &t[1].y, &t[2].x, &t[2].y) != EOF) {
		if(!(t[0].x || t[0].y || t[1].x 
		     || t[1].y || t[2].x || t[2].y))
			break;
		printf("%d\n", grid_inside(3, t));
	}
    return 0;
}