POJ 1265 /// 皮克定理+多边形边上整点数+多边形面积

题目大意：

默认从零点开始

给定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==0 && dy==0) return 0;
    return gcd(dx,dy)-1; // 不包括a b两个顶点
}
// 求多边形边上的整点数
int liPg() {
    int res=0;
    for(int i=1;i<n;i++)
        res+=lineSeg(p[i],p[i+1]);
    res+=lineSeg(p[n],p[1]);
    return res+n; // +n 是加上n边形的n个顶点

#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;

double eps=1e-10;
double add(double a,double b) {
    if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
    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[105];
int n;
int gcd(int a,int b) {
    while(b) {
        int t=a%b;
        a=b; b=t;
    } return a;
}
//求多边形的面积
double areaPg() {
    double res=0;
    for(int i=1;i<=n;i++)
        res+=(p[i]-p[0]).det(p[i+1]-p[0]);
    return res/2;
}
//求线段ab之间的整点数
int lineSeg(P a,P b) {
    int dx=abs(a.x-b.x), dy=abs(a.y-b.y);
    if(dx==0 && dy==0) return 0;
    return gcd(dx,dy)-1;
}
int liPg() {
    int res=0;
    for(int i=1;i<n;i++)
        res+=lineSeg(p[i],p[i+1]);
    res+=lineSeg(p[n],p[1]);
    return res+n;
}

int main()
{
    int t; scanf("%d",&t);
    for(int o=1;o<=t;o++) {
        scanf("%d",&n);
        p[0].x=p[0].y=0;
        for(int i=1;i<=n;i++) {
            double a,b; scanf("%lf%lf",&a,&b);
            p[i].x=p[i-1].x+a, p[i].y=p[i-1].y+b;
        }
        double s=areaPg();
        int li=liPg();
        int in=(int)s-li/2+1;
        printf("Scenario #%d:
",o);
        printf("%d %d %.1f
",in,li,s);
    }

    return 0;
}