poj-1265-Area-pick定理

一条定理：
1.以格子点为顶点的线段，覆盖的点的个数为易做图(dx,dy)，其中，dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0，则覆盖的点数为dy或dx。
2.Pick公式：平面上以格子点为顶点的简单多边形，如果边上的点数为on，内部的点数为in，则它的面积为A=on/2+in-1。
3.任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和（黑书上有说明）
[html]  
#include<iostream>  
#include<stdio.h>  
#include<algorithm>  
#include<string.h>  
using namespace std;  
int dx[100001];  
int dy[100001];  
int 易做图(int a,int b)  
{  
    if(b==0) return a;  
    else return 易做图(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++)  
        {  www.zzzyk.com
            num+=易做图(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);  
    }  
}

补充：软件开发 , C++ ,