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;}