poj 1265 Area【计算几何：叉积计算多边形面积+pick定理计算多边形内点数+计算多边形边上点数】

题目：http://poj.org/problem?id=1265

Sample Input

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

Sample Output

Scenario #1:

0 4 1.0

Scenario #2:

12 16 19.0

注意：题目给出的成对的数可不是坐标，是在x和y方向走的数量。


边界上的格点数：一条左开右闭的线段（x1, x2）->（x2, y2）上的格点数为：gcd( abs(x2-x1), abs(y2-y1) );
Pick公式：对于给定的坐标都是整点的简单多边形，有如下等式：
多边形面积=多边形内部格点数+边上的格点数/2 - 1；  由此可以推出如何计算多边形内部的格点数量！
当然这需要知道多边形的面积，计算多边形的面积：顺时针或逆时针相邻两点分别与原点构成的向量的叉积累加和，再取绝对值，再除2。
（因为顺逆方向的问题，可能会导致叉积累加和为负，又因为叉积计算的是向量围成的四边行的面积所以还要除2）

代码：

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <math.h>

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

struct node

{

    int x;

    int y;

}q[110];

int cal_area(node a, node b)

{

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

} //叉积计算两个向量的面积

int gcd(int a, int b)

{

    return b==0?a:gcd(b,a%b);

}

int main()

{

    int tg; scanf("%d", &tg);

    int n;

    int i, j;

    for(int cnt=1; cnt<=tg; cnt++){

        scanf("%d", &n);

        q[0].x=0; q[0].y=0; //这是坐标原点

        int p_on_l=0; //point on line

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

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

           //先计算线段上的点数

           int dx=abs(q[i].x);

           int dy=abs(q[i].y);

           p_on_l+=gcd(dx, dy);

           q[i].x+=q[i-1].x;

           q[i].y+=q[i-1].y; //题目中给出的是前一个点在x y方向上行走的数量

        }                    //只要累加就可以计算出i节点的坐标

        //所有点的坐标计算完毕

        int area=0;

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

            area+=cal_area(q[i], q[i-1]);

        }

        area=abs(area); //多边行的面积一定大于等于0 如果求出的结果为负值

                        //说明叉积计算的方向是和正值计算相比是反的

        double ans=area/2.0;//叉积计算的是平行四边行的面积 不是三角形 面积要减半

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

        printf("%d %d %.1lf\n", (area/2+1-p_on_l/2), p_on_l, ans);

        printf("\n");

    }

    return 0;

}

poj 1265 Area【计算几何：叉积计算多边形面积+pick定理计算多边形内点数+计算多边形边上点数】的相关教程结束。