Area - POJ 1265（pick定理求格点数+求多边形面积）

题目大意：以原点为起点然后每次增加一个x，y的值，求出来最后在多边形边上的点有多少个，内部的点有多少个，多边形的面积是多少。

分析：

1、以格子点为顶点的线段，覆盖的点的个数为GCD(dx,dy)，其中，dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0，则覆盖的点数为dy或dx。
2、Pick公式：平面上以格子点为顶点的简单多边形的面积=边上的点数/2+内部的点数+1。
3、任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和。

代码如下：

-------------------------------------------------------------------------------------------------------------

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<math.h>

using namespace std;

const int MAXN = 1e4+;

const double EPS = 1e-;

int GCD(int m, int n)

{

    if(!m || !n)

        return m+n;

    return GCD(n, m%n);

}

int main()

{

    int T, t=;

    scanf("%d", &T);

    while(T--)

    {

        int N, x, y, nx=, ny=, cnt=, area=;

        scanf("%d", &N);

        for(int i=; i<N; i++)

        {

            scanf("%d%d", &x, &y);

            cnt += GCD(abs(x), abs(y));

            x += nx, y += ny;

            area += (x*ny - y*nx);

            nx = x, ny = y;

        }

        if(area < )area = -area;

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

        printf("%d %d %.1f\n\n", (area-cnt)/+, cnt, area/2.0);

    }

    return ;

}

巴特西

Area - POJ 1265（pick定理求格点数+求多边形面积）

最新文章

热门文章