皮克公式 Peake’s theorem

皮克公式是奥地利数学家皮克发现的一个计算点阵中多边形的面积公式．

简单说就是在一个坐标纸、表格纸、点阵纸上，有一个所有顶点都在点上的多边形，那么这个多边形的面积满足：

其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积
例如：

2
4
1 0
0 1
-1 0
0 -1
7
5 0
1 3
-2 2
-1 0
0 -3
-3 1
0 -3

Scenario #1:
0 4 1.0

Scenario #2:
12 16 19.0

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator

这道题让你求的是多边形边界，内部有几个点以及多边形的面积。要用到皮克公式

Pick公式：平面上以格子点为顶点的简单多边形的 面积 = 边上的点数/2+内部的点数-1。

任意一个多边形的面积等于 :按顺序 求相邻两个点与原点组成的向量的叉积之和/2（可以利用三角形求证，需要取绝对值 二维叉积公式：x1y2-x2y1）。这里面我们可以把原点设置为0。0点。

以格子点为顶点的线段，其覆盖的点的个数为GCD(dx,dy)，dxdy分别为线段横向坐标差值和纵向差值。如果dx或dy为0，则覆盖的点数为dy或dx（此时平行于坐标轴）。
注意这道题里面输入的是dx，dy不是每一个点的坐标，而是沿着x轴，y轴方向走了多少步。所以要想办法把每一个点的坐标求出来，可以通过每一步走步和前一个点想加来求出点的坐标。

#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=10005;
int n;
struct Line{
    int x,y;
}line[MAXN];
int det(Line l1,Line l2){
    return l1.x*l2.y-l2.x*l1.y;
}
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
double poloygonArea(Line* l,int n){
    double area;
    for(int i=2;i<=n;i++){
        area=area+det(l[i],l[i-1]);
    }
    return fabs(area/2);
}
int main(){
    int t;
    cin>>t;
    int kase=0;
    while(t--){
        cin>>n;
        double ans=0;//计算多边形内部的格点数
        for(int i=1;i<=n;i++){
            scanf("%d%d",&line[i].x,&line[i].y);
            ans=ans+gcd(abs(line[i].x),abs(line[i].y));
            line[0].x=0;
            line[0].y=0;
            line[i].x=line[i].x+line[i-1].x;
            line[i].y=line[i].y+line[i-1].y;
        }
        double area=poloygonArea(line,n);
        double edge=area+1-ans/2;
        printf("Scenario #%d:\n",++kase);
        printf("%d %d %.1lf\n",(int)edge,(int)ans,area);
        printf("\n");
    }
    return 0;
}

链接：https://www.nowcoder.net/acm/contest/75/I
来源：牛客网

题目描述

 

给你一个三角形的顶点A,B,C的坐标（坐标都为整数），请求出三角形的面积，三角形内的点的个数以及边AB、BC和AC边上的点的个数（不包括顶点ABC）

输入描述:

多组输入
每组输入三行,每行两个整数
第一行顶点A的坐标Xa,Ya.
第二行顶点B的坐标Xb,Yb.
第三行顶点C的坐标Xc,Yc.
0<=X,Y<=1,000,000
输入-1结束输入

输出描述:

每组输出一行，输出一个实数（保留一位小数），四个整数，分别代表三角形面积，三角形内的点的个数以及边AB、BC和AC边上的点的个数，每个数用空格隔开。

#include <iostream> 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
#include <math.h> 
using namespace std;
#define LL long long 
long long int gcd(long long int a, long long int b)
{
    //cout << a << " x " << b << endl;
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a%b);
    }
}
int main()
{
    long long int x[3], y[3];
    while (cin >> x[0] && x[0] != -1)
    {
        cin >> y[0];
        for (int s = 1; s <= 2; s++)
        {
            cin >> x[s] >> y[s];
        }
        long long int bian = gcd(fabs(x[0] - x[1]), fabs(y[0] - y[1])) + gcd(fabs(x[1] - x[2]), fabs(y[1] - y[2])) + gcd(fabs(x[2] - x[0]), fabs(y[2] - y[0]));
        //s=a+b/2-1;
        //cout << bian << endl;
        double s = fabs((x[0] * y[1] + x[1] * y[2] + x[2] * y[0] - x[0] * y[2] - x[1] * y[0] - x[2] * y[1])) / 2;
        long long int neibu = (s + 1 - bian / 2);
        printf("%.1lf %lld %lld %lld %lld\n", s, neibu, gcd(fabs(x[0] - x[1]), fabs(y[0] - y[1]))-1, gcd(fabs(x[1] - x[2]), fabs(y[1] - y[2]))-1, gcd(fabs(x[2] - x[0]), fabs(y[2] - y[0]))-1);
    }
    return 0;
}