poj-1265-Area-pick定律

poj-1265-Area-pick定理

一条定理：

1.以格子点为顶点的线段，覆盖的点的个数为GCD(dx,dy)，其中，dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0，则覆盖的点数为dy或dx。

2.Pick公式：平面上以格子点为顶点的简单多边形，如果边上的点数为on，内部的点数为in，则它的面积为A=on/2+in-1。

3.任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和（黑书上有说明）

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int dx[100001];
int dy[100001];
int gcd(int a,int b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
int area(int i,int j)
{
    return dx[i]*dy[j]-dy[i]*dx[j];
}
int main()
{
    int N,cas,i,n;
    scanf("%d",&N);
    for(cas=1;cas<=N;cas++)
    {
        cin>>n;
        dx[0]=0;
        dy[0]=0;
        n++;
        int xx,yy;
        for(i=1;i<n;i++)
        {
            cin>>xx;
            cin>>yy;
            dx[i]=xx+dx[i-1];
            dy[i]=yy+dy[i-1];
        }
        n--;
        int num;
        int s;
        num=s=0;
        for(i=0;i<n;i++)
        {
            num+=gcd(abs(dx[i]-dx[(i+1)%n]),abs(dy[i]-dy[(i+1)%n]));
            s+=area(i,(i+1)%n);
        }
        if(s<0) s=-s;
        int I;
        I=(s-num+2)*0.5;
        printf("Scenario #%d:\n",cas);
        printf("%d %d %.1lf\n\n",I,num,s*0.5);
    }
}