本文共 1471 字，大约阅读时间需要 4 分钟。

这道题自己想了个方法：遍历矩形区域(xmin, ymin, xmax, ymax)内的所有点，看是否落在两边之间。

然后就TLE了。

网上查解题报告。知道了pick定理:http://en.wikipedia.org/wiki/Pick's_theorem

//pick theorem

多边形的面积（取整）等于多边形内部的整数点个数(i) 加上边界整数点个数(b)的一半再减一。

证明方法见上述维基百科与http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm

我没有看啊。。。老了。。。

三角形的面积在知道三个顶点位置后可通过下面的公式得出：

//A = 0.5 * abs((x1 - x3)(y2 - y1) - (x1 - x2)(y3 - y1))

见http://en.wikipedia.org/wiki/Triangle

三角形一条边上的所有整数点（包括顶点）可以首先将这条边移到(0, 0)->(x, y)。这时，（x/gcd(x,  y), y/gcd(x, y)）肯定在这条边上，并且是整数点，其余所有整数点的可以表示为k(x/gcd(x,  y), y/gcd(x, y))。所以所有的整数点个数为gcd(x, y) + 1。即：

//b = gcd(x, y) + 1

这里解释得比较清楚:http://www.darkswordzone.com/?p=974

在上述A, b求出后（b = b1 + b1 + b3 - 3, 减去算了两边的三个顶点，因为顶点在题中一定是整数点），我们有：

代码如下：

#include 
   
    using namespace std;//pick theorem//A = i + b / 2 - 1//A = 0.5 * abs((x1 - x3)(y2 - y1) - (x1 - x2)(y3 - y1))//b = gcd(x, y) + 1//i = A + 1 - b / 2int gcd(int x, int y){	if(x > y)	{		if(y == 0)			return x;		else			return gcd(x - y, y);	}	else	{		if(x == 0)			return y;		else			return gcd(y - x, x);	}}int main(){	int x1, y1, x2, y2, x3, y3;	while(true)	{		cin>>x1>>y1>>x2>>y2>>x3>>y3;		if(!x1 && !y1 && !x2 && !y2 && !x3 && !y3)		{			return 0;		}		int A = 0.5 * abs((x1 - x3) * (y2 - y1) - (x1 - x2) * (y3 - y1));		int b1 = gcd(abs(x2 - x1), abs(y2 - y1)) + 1;		int b2 = gcd(abs(x3 - x1), abs(y3 - y1)) + 1;		int b3 = gcd(abs(x3 - x2), abs(y3 - y2)) + 1;		int i = A + 1 - (b1 + b2 + b3 - 3) / 2;		cout<
    <
   

转载地址：http://lxxli.baihongyu.com/