poj 1265Area解题报告

链接：http://poj.org/problem?id=1265

pick定理，如果一个多边形的每个顶点都在一个坐标系的整数点上，即格子点上，那么其内部包含的点in和边上的点on以及多边形的面积的关系是s=in+on/2-1;还要用到多边形的面积为从原点到两个相邻顶点的向量的叉积的和。以及两个格子点之间的连线上格子点的数目为gcd(abs(x1-x2),abs(y1-y2));

#include<stdio.h>
#define M 105
int x[M],y[M];
int gcd(int a,int b)
{
    if(!a)
    return b;
    int c;
    while(b)
    {
        c=b;
        b=a%b;
        a=c;
    }
    return a;
}
int abs(int a)
{
    return a>0?a:-a;
}
int main()
{
    int area,i,j,k,t,n,e,tx,ty,in;
    scanf("%d",&t);
    x[0]=y[0]=0;
    int icase=1;
    while(t--)
    {
        scanf("%d",&n);
        area=e=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&tx,&ty);
            x[i]=x[i-1]+tx;
            y[i]=y[i-1]+ty;
            e+=gcd(abs(tx),abs(ty));
            area+=x[i-1]*y[i]-x[i]*y[i-1];
        }
        in=(area-e+2)/2;
        printf("Scenario #%d:\n",icase++);
        printf("%d %d %.1lf\n\n",in,e,area/2.0);
    }
    return 0;
}