//poj_1256 Area
//坐标图上的多边形，求多边形内部点数，边上点数，多边形面积。
//Pick公式：S=I+E/2-1，即多边形的面积=在多边形内的格点数+在多边形边上的格点数/2-1
//先用叉积求多变形面积，再根据公式计算内部点数量
//边界格点数---利用斜边对应的直角边的最大公约数

#include<iostream>
#include<cmath>
using namespace std;

int gcd(int a,int b)//最大公约数
{
    while(b)
    {
        int temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

int get_area(int x1,int y1,int x2,int y2)//叉积求三角形面积
{
    return (x1*y2-x2*y1);
}

int main()
{
    //freopen("in.txt","r",stdin);
    int i,t,n,area,in,on;
    int x1,y1,x2,y2,x,y;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        x1=y1=0;
        area=on=0;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d%d",&x,&y);
            on+=gcd(abs(x),abs(y));//求边上点的个数
            x2=x1+x;
            y2=y1+y;
            area+=get_area(x1,y1,x2,y2);
            x1=x2;
            y1=y2;
        }
        in=area/2-on/2+1;
        printf("Scenario #%d:\n%d %d %.1lf\n\n",i,in,on,area/2.0);
    }
    return 0;
}
本页面高亮代码使用codeHl生成，查看详情