POJ 2954 Triangle(頂点の多角形を整えて含む点数を求めます)

POJ 2954 Triangle(頂点の多角形を整えて含む点数を求めます)
http://poj.org/problem?id=2954
タイトル:
       3つの整点からなる三角形をあげて、この三角形の内部の整点の個数を求めます.
分析:
       Pickの定理によって、1つの多角形はすべての頂点がすべて整点から構成するならば、この多角形の面積はSで、この多角形の辺の上の整点はLで、内部の整点はNで、あります:
       N+L/2-1=S.
       では、この三角形の面積と三角形の辺にいったい何個の整点があるかを求めればよい.面積は直接フォークで求めればよい.以下、三角形の各辺に何個の整点があるかを求めればよい.
       2つの整点からなる線分があると仮定し、その線分X方向の増分絶対値はDX、Y方向の増分絶対値はDYである.線分内部(端点を含まない)の整点個数をansとする.
       DX=DY=0の場合、ans=0
       DX=0の場合、ans=DY-1(gcd(DX,DY)-1と等価)
       DY=0の場合、ans=DX-1(gcd(DX,DY)-1に相当)
       DX!=0かつDY!=0の場合、ans=gcd(DX,DY)-1
       上記の結論を簡単に説明します.
       端点が整点である線分の内部に整点があれば、線分は必ず内部の整点によって均一に分割される.
線分の内部に5つの整点(この5つの整点は必ず均一に配列されている)があると仮定すると、両端点を含めて7つの整点があり、線分は6等分されている.実はDXとDYはそれぞれ6等分されているので、DXとDYの最大公約数=6.DXとDYの最大公約数=8であれば、線分は一定で最大8等分され、線分の端点が整点であるため、だから8等分の各点は整点です.
ACコード:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double Area(Point A,Point B,Point C)
{
    return fabs(Cross(A-B,B-C))/2;
}
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int get_segment_point(Point A,Point B)//               
{
    int dx=fabs(A.x-B.x),dy=fabs(A.y-B.y);
    if(dx==0 && dy==0) return 0;
    return gcd(dx,dy)-1;
}

int main()
{
    int x1,y1,x2,y2,x3,y3;
    while(scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)==6)
    {
        if(x1==0&&y1==0&&x2==0&&y2==0&&x3==0&&y3==0) break;
        Point A(x1,y1),B(x2,y2),C(x3,y3);
        int S=Area(A,B,C);//  
        int L=3+get_segment_point(A,B)+get_segment_point(B,C)+get_segment_point(A,C);//   
        printf("%d
",S+1-L/2);
    }
    return 0;
}