POJ 2954解題レポート

この問題は自分で方法を考えた:矩形領域(xmin,ymin,xmax,ymax)内のすべての点を遍歴して、両側の間に落ちるかどうかを見た.
そしてTLEです.
ネットで問題を解く報告書.ピックの定理を知った:http://en.wikipedia.org/wiki/Pick's_theorem
//pick theorem//A = i + b/2 - 1
ポリゴンの面積(整列)は、ポリゴン内部の整数点個数(i)に境界整数点個数(b)の半分を加えてさらに減算される.
証明方法は上記ウィキペディアとhttp://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm
見てないよ..年をとった...
三角形の面積は、3つの頂点の位置を知ってから、次の式で得られます.
//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=b 1+b 1+b 1+b 3-3、両側の3つの頂点を減算します.頂点は問題の中で必ず整数点であるからです).私たちは//i=A+1-b/2があります.
コードは次のとおりです.

#include <iostream>
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 / 2

int 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<<i<<endl;
	}
}