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;
} 
查看45道真题和解析
