HDU1705 (Count the grid)[计算几何，皮克公式]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1705

题目大意：有一个在格纸上的三角形，给定三个顶点的坐标，求在三角形内部的格点数。

皮克定理：对于一个所有顶点都为整点的简单多边形，其面积为S，内部格点数为n，边上格点数为s， 则有：S = n + s/2 – 1

这题求边上格点数时可以发现如果边不是水平或竖直的，那么边上的格点数为GCD(a,b)+1，a和b分别为边的水平和竖直方向上的长度。
求面积时要用叉积，直接套海伦公式会因为浮点数误差无法通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct Point {
    int x,y;
    Point() {}
    Point(int _x,int _y) {
        x=_x;
        y=_y;
    }
    int operator ^(const Point &b) const {
        return x*b.y-y*b.x;
    }
    Point operator -(const Point &b) const {
        return Point(x-b.x,y-b.y);
    }
    int operator *(const Point& b) const {
        return x*b.x+y*b.y;
    }
};
int gcd(int a,int b) {
	if(!b) return a;
	return gcd(b,a%b);
}
int getns(int x1,int y1,int x2,int y2) {
	if(x1==x2) return abs(y2-y1)+1;
	if(y1==y2) return abs(x2-x1)+1;
	return gcd(abs(x2-x1),abs(y2-y1))+1;
}
int main() {
	int x1,y1,x2,y2,x3,y3;
	int s=0;
	int S;
	while(~scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)) {
		if(x1==y1 && y1==x2 && x2==y2 && y2==x3 && x3==y3 && y3==0) break;
		s=0;
		s+=getns(x1,y1,x2,y2);
		s+=getns(x1,y1,x3,y3);
		s+=getns(x2,y2,x3,y3);
		s-=3;
		S=abs(Point(x1-x2,y1-y2)^Point(x3-x2,y3-y2));
		printf("%d\n",(S-s+2)/2);
	}
}