poj-1265-Area-pick定理

一條定理： 1.以格子點為頂點的線段，覆蓋的點的個數為GCD(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 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++)           {  www.2cto.com             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);       }   }