pick定理详解

一、概念

　　假设P的内部有I(P)个格点，边界上有B(P)个格点，则P的面积A(P)为：A(P)=I(P)+B(P)/2-1。

二、说明

　　Pick定理主要是计算格点多边形（定点全是格点的不自交图形）P的面积与其边界和内部格点数之间的关系。

　　格点多边形的面积A(P)可以通过叉积计算出来，不过叉积计算出来的面积是实际面积的2倍；

　　边界上的格点B(P)可以通过计算相邻两点的横坐标之差与纵坐标之差的最大公约数的和得到；

　　内部的格点I(P)则通过公式得：I(P) = A(P)-B(P)/2+1计算出。

　　解释：

　　　a.关于边界格点计算两点横纵坐标之差就是以两个点构成的边做坐标轴，组成的三角形（或者线）的两个之角标求gcd

　　　b.格点多边形的面积是通过将多边形固定一个点，然后在遍历每两个点，三个点构成的三角形求面积。由于叉积可以为负，所以不必担心多加的三角形或者不在多边形内部的三角形，都会减去。

三、代码

#include <stdio.h>

#include <math.h>

#include<stdlib.h>

struct node

{

    int x,y;

} point[];

int gcd(int a,int b)//gcd

{

    if(b==)

        return a;

    return

        gcd(b,a%b);

}

int Area(node a,node b)//叉积

{

    return a.x*b.y-a.y*b.x;

}

int main()

{

    int T,case1=;

    scanf("%d",&T);

    int n;

    while(T--)

    {

        int a=,p=,dx,dy,i;

        scanf("%d",&n);

        point[].x=;

        point[].y=;

        for(i=; i<=n; i++)

        {

            scanf("%d%d",&point[i].x,&point[i].y);

            /*求每条边上的点*/

            dx=abs(point[i].x);

            dy=abs(point[i].y);

            p+=gcd(dx,dy);

            /*用叉积求面积*/

            point[i].x+=point[i-].x;

            point[i].y+=point[i-].y;

            a+=Area(point[i],point[i-]);

        }

        /*最后面积要取正值*/

        a=abs(a);

        printf("Scenario #%d:\n",case1++);

        printf("%d %d %.1f\n\n",(a-p+)/,p,0.5*a);

    }

    return ;

}

巴特西

pick定理详解

一、概念

二、说明

最新文章

热门文章