题目大意：
默认从零点开始
给定n次x y上的移动距离
组成一个n边形（可能为凹多边形）
输出其 内部整点数 边上整点数 面积
皮克定理
多边形面积s = 其内部整点in + 其边上整点li / 2 - 1
那么求内部整点就是 in = s + 1 - li / 2
求整个多边形边上的整点数
//求两点ab之间的整点数
int lineSeg(P a,P b) {
int dx=abs(a.x-b.x), dy=abs(a.y-b.y);
if(dx== && dy==) return ;
return gcd(dx,dy)-; // 不包括a b两个顶点
}
// 求多边形边上的整点数
int liPg() {
int res=;
for(int i=;i<n;i++)
res+=lineSeg(p[i],p[i+]);
res+=lineSeg(p[n],p[]);
return res+n; // +n 是加上n边形的n个顶点
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std; double eps=1e-;
double add(double a,double b) {
if(abs(a+b)<eps*(abs(a)+abs(b))) return ;
return a+b;
}
struct P {
double x,y;
P(){};
P(double _x,double _y):x(_x),y(_y){};
P operator - (P p) {
return P(add(x,-p.x),add(y,-p.y)); }
P operator + (P p) {
return P(add(x,p.x),add(y,p.y)); }
P operator * (double d) {
return P(x*d,y*d); }
double dot (P p) {
return add(x*p.x,y*p.y); }
double det (P p) {
return add(x*p.y,-y*p.x); }
}p[];
int n;
int gcd(int a,int b) {
while(b) {
int t=a%b;
a=b; b=t;
} return a;
}
//求多边形的面积
double areaPg() {
double res=;
for(int i=;i<=n;i++)
res+=(p[i]-p[]).det(p[i+]-p[]);
return res/;
}
//求线段ab之间的整点数
int lineSeg(P a,P b) {
int dx=abs(a.x-b.x), dy=abs(a.y-b.y);
if(dx== && dy==) return ;
return gcd(dx,dy)-;
}
int liPg() {
int res=;
for(int i=;i<n;i++)
res+=lineSeg(p[i],p[i+]);
res+=lineSeg(p[n],p[]);
return res+n;
} int main()
{
int t; scanf("%d",&t);
for(int o=;o<=t;o++) {
scanf("%d",&n);
p[].x=p[].y=;
for(int i=;i<=n;i++) {
double a,b; scanf("%lf%lf",&a,&b);
p[i].x=p[i-].x+a, p[i].y=p[i-].y+b;
}
double s=areaPg();
int li=liPg();
int in=(int)s-li/+;
printf("Scenario #%d:\n",o);
printf("%d %d %.1f\n",in,li,s);
} return ;
}