三角形内部の整点の個数


タイトル:
            ,             。

問題:
s=l/2+n-1;
s:             。
l:     ;
n:          。

//数式は自分で探す
#include//s=l/2+n-1;
#include
#include
int a,b,c,d,e,f;
int area(){
    return abs((a*d+c*f+b*e-a*f-b*c-d*e)/2);
}
int gcd(int x,int y)
{
    if(y==0)return x;
    else
        return gcd(y,x%y);
}
int main ()
{
    int t;scanf("%d",&t);
    int k=0;
    while(t--)
    {
        scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
        int s=area();
        int l1=gcd(abs(a-c),abs(b-d));
        int l2=gcd(abs(a-e),abs(b-f));
        int l3=gcd(abs(c-e),abs(d-f));
        printf("CASE %d: %d
"
,++k,s-(l1+l2+l3)/2+1); } return 0; }