【给小学奥数跪了-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; }