Area(pick定理)

http://poj.org/problem?id=1265

题意：起始为（0,0），给出每个点的偏移量，求依次连接这些点形成的多边形边界上格点的个数。

思路：先将各个点的坐标求出存入，由pick定理知：

面积 = 内部格点数目+边上格点数目/2-1；

每条边边格点数目 = gcd(x2-x1,y2-y1)；

内部格点数目 = 面积+1-边界格点数目/2；

 #include <stdio.h>

 #include <stdlib.h>

 #include <math.h>

 #include <algorithm>

 using namespace std;

 struct node

 {

     int x;

     int y;

 } point[];

 double area_polygon(int n)//求多边形面积

 {

     double s1=,s2=;

     int i;

     for (i=; i<=n; i++)

        {

            s1+=point[i%n].y*point[i-].x;

            s2+=point[i%n].y*point[(i+)%n].x;

        }

     return fabs(s1-s2)/;

 }

 int main()

 {

     int t,o = ;

     scanf("%d",&t);

     while(t--)

     {

         ++o;

         int n,dx,dy,cnt = ;

         point[].x = ;

         point[].y = ;

         scanf("%d",&n);

         for (int i = ; i <= n; i++)

         {

             scanf("%d %d",&dx,&dy);

             point[i].x = point[i-].x+dx;//存入各点坐标（前一个坐标加偏移量）

             point[i].y = point[i-].y+dy;

             cnt += __gcd(abs(point[i].x-point[i-].x),abs(point[i].y-point[i-].y));

             //cnt代表边上的点

         }

         double A = area_polygon(n);

         int inpoint = A+-cnt/;//pick定理（面积 = 内部格点数目+边上格点数目-1）

         printf("Scenario #%d:\n",o);

         printf("%d %d %.1f\n\n",inpoint,cnt,A);

     }

     return ;

 }