2954 Triangle

問題概要

格子点を結んだ三角形が与えられる。
三角形の真に内部に含まれる格子点の個数を求めよ。

解法

ピックの定理。
格子点を結んだ多角形について、
面積=内部の点+辺上の点/2-1が成り立つ。

辺上の格子点の数はgcd(dx,dy)により求められる。

ソースコード

int main(){
	int x[3],y[3];
	for(;;){
		scanf("%d%d%d%d%d%d",x,y,x+1,y+1,x+2,y+2);
		
		bool nz=0; rep(i,3)nz=nz||x[i]||y[i];
		if(!nz)break;
		
		int a=x[1]-x[0],b=y[1]-y[0],c=x[2]-x[0],d=y[2]-y[0];
		ll area2=ll(a)*d-ll(b)*c; if(area2<0)area2*=-1;
		int edge=0;
		rep(i,3){
			int dx=abs(x[i]-x[(i+1)%3]),dy=abs(y[i]-y[(i+1)%3]);
			edge+=dx||dy?__gcd(dx,dy):dx+dy;
		}
		ll ans=(area2+2-edge)/2;
		printf("%d\n",ans);
	}
	return 0;
}