三角形内部の整点の個数
タイトル:
問題:
//数式は自分で探す
, 。
問題:
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;
}