Area Pick定理加叉积三角剖分
/*注意由于叉积的有向面积，进行剖分累加的时候一定要在最后取绝对值。不能在中间过程取。否则和会变大。*/#include <iostream>#include <stdio.h>#include <cmath>#define sum(a,b,c) ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))using namespace std;struct po{ int x,y;} point[105];int gcd(int n,int m){ if(m==0||n==0) return fabs(m-n); else if(n%m==0) return m; else return gcd(m,n%m);}int main(){ int t; scanf("%d",&t); for(int k=1; k<=t; k++) { int n; int count=0; scanf("%d",&n); point[1].x=point[1].y=0; for(int j=2; j<=n+1; j++) { scanf("%d %d",&point[j].x,&point[j].y); point[j].x=point[j].x+point[j-1].x; point[j].y=point[j].y+point[j-1].y; } for(int i=2; i<=n+1; i++) count+=gcd(fabs(point[i].x-point[i-1].x),fabs(point[i].y-point[i-1].y)); count+=gcd(fabs(point[n+1].x-point[1].x),fabs(point[1].y-point[n+1].y)); double summ=0; for(int i=2; i<=n; i++) summ+=sum(point[1],point[i],point[i+1]); summ=summ/2; int ge=summ+1-count/2; printf("Scenario #%d:\n",k); printf("%d %d %.1lf\n",ge,count,summ); printf("\n"); } return 0;}