poj1265，皮克定理：多边形面积，边点数，内部点数

😎皮克定理：

S:多边形面积 ——累加叉积/2

I:多边形内部点数

E:多边形边上的点数——每次求出端点的最大公约数，其他约数构成最小子增加，最大公约数就是可以放大多少次，就是新增的点数，

每次起点不计，终点计入，因为是封闭多边形，所以最开始的起点是最后的终点

#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Point{
	int x,y;
	Point(int x=0,int y=0):x(x),y(y){
	};
	Point operator-(Point b){return Point(x-b.x,y-b.y);
	}
	double operator^(Point b){return x*b.y-y*b.x;
	}
	Point operator+(Point b){return Point(x+b.x,y+b.y);
	}
};
const int N=105;
Point point[N];

int t,m,xx,yy;
int I,e;
double s;

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

double calArea(){
	double area=0;
	for(int i=0;i<m;i++){
		area+=(point[i]^point[(i+1)%m])/2;//用公式叉积/2求出面积 
	}
	return fabs(area);//逆时针为正，顺时针为负，为防止负求绝对值 
}

int main() {
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		s=I=e=0;
		scanf("%d",&m);//输入运动数 
		for(int j=0;j<m;j++){
			scanf("%d%d",&xx,&yy);//输入运动方案 
			point[j].x=xx;point[j].y=yy;//如果为第一次，直接记录xx，yy位置 
			if(j) point[j]=point[j-1]+Point(xx,yy);//不是第一次在前一次基础上运动 
			e+=gcd(abs(xx),abs(yy));//记住abs ，此处为一次运动新增点数 
		}
		s=calArea();//计算面积 
		I=(int)s+1-e/2;//计算内部点数，皮克定理 
		printf("Scenario #%d:\n%d %d %.1f\n\n",i,I,e,s);
	}
	return 0;
}