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