1265 Area
問題概要
座標平面上の格子点を結んだ多角形が与えられる。
この多角形の内部の格子点の個数、辺上の格子点の個数、面積を出力せよ。
解法
辺上の格子点の個数は、辺ごとにそれぞれgcd(dx,dy)で求まる。
また、多角形の面積も外積から求まる。
ピックの定理という、内部の格子点の個数I,辺上の格子点の個数E,面積Aの間に成り立つ次のような関係がある。
A=I+E/2-1
ここからIも求められる。
ソースコード
int main() { int CS; scanf("%d",&CS); rep(cs,CS){ int n,x[100],y[100],dx,dy,E=0,I=0; scanf("%d",&n); G g; rep(i,n){ scanf("%d%d",&dx,&dy); if(i>0)x[i]=x[i-1]+dx,y[i]=y[i-1]+dy; g.pb(P(x[i],y[i])); dy=abs(dy); dx=abs(dx); if(dx>dy)swap(dx,dy); if(dx==0)E+=dy; else E+=__gcd(dy,dx); } double A=area2(g)/2; I=int(A+1-E/2.0); printf("Scenario #%d:\n",cs+1); printf("%d %d %.1f\n\n",I,E,A); } return 0; }