【给小学奥数跪了-Pick公式与欧几里德算法】poj1265—Area

这个题最早的来源是小学奥数，六年级的时候，我们学到了格点的面积……求格点内的面积公式，又叫PICK公式。当然我只能呵呵了，完全不记得有这个公式……

由上图得，S=N+L/2-1,N属于格子内的点，L属于边划过的格子。

INPUT给的是绘图路径而不是坐标，所以说需要转化成坐标，求擦过边的点，可以用GCD（点A,点B）来实现，可以用史上最古老的算法——欧几里德算法，LOG(N)的效率。

现在小学六年级就学这么IMBA的东西，我真的无奈了！依稀记得当年会了个鸡兔同笼高兴的和个什么似的。

#include <iostream>                                                         #include <cmath>                                                            #include <iomanip>                                                          using namespace std;                                                                                                                                    class point                                                                 {                                                                           public:                                                                    int x;                                                                    int y;                                                                                                                                               };                                                                          point inpath[300];                                                                                                                                      int gcd(int a,int b)                                                        {                                                                           if(a==0)                                                                   return b;                                                                 if(b==0)                                                                   return a;                                                                                                                                            return gcd(b,a%b);                                                                                                                                    }                                                                                                                                                       int pinside(point a,point b)                                                {                                                                           return gcd(abs(a.x-b.x),abs(a.y-b.y));                                    }                                                                                                                                                       double getarea(int n)                                                       {                                                                            double result=0;                                                           for(int i=0;i<n;i++)                                                       {                                                                           int a=inpath[(i+1)%n].x;                                                 int b=inpath[(i+1)%n].y;                                                 result+=((inpath[i].y*a)-(inpath[i].x*b))*1/2.0;                         }                                                                         return fabs(result);                                                       }                                                                           int main()                                                                  {                                                                            int testcase;                                                              cin>>testcase;                                                             for(int i=0;i<testcase;i++)                                                {                                                                            int n;                                                                   cin>>n;                                                                  int intmpx,intmpy,totalx=0,totaly=0;                                     int onsideco=0,inmapco=0;                                                double area=0;                                                           for(int k=0;k<n;k++)                                                     {                                                                         cin>>intmpx>>intmpy;                                                totalx+=intmpx;                                                         totaly+=intmpy;                                                         inpath[k].x=totalx;                                                     inpath[k].y=totaly;                                                      }                                                                                                                                                   for(int j=0;j<n;j++)                                                      {                                                                         onsideco+= pinside(inpath[j],inpath[(j+1)%n]);                          }                                                                     area=getarea(n);                                                         //由公式方便得到s=i+e/2-1,然后倒推得里面的点                                                                                                      inmapco=(area+1)-(onsideco/2.0);                                                                                                                                                                                           cout<<"Scenario #"<<i+1<<":"<<endl;                                      cout<<inmapco<<" "<<onsideco;                                            cout<<setiosflags(ios::fixed)<<setprecision(1)<<" "<<area<<endl;         cout<<endl;                                                                                                                                       }                                                                                                                                                                                                                               return 0;                                                                  }