POJ 1265 Area(面积，pick公式)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一些移动向量，最终形成一个多边形，求多边形的面积。以为多边形内部的格点数目和多边形边上的格点数目 。
首先面积可以通过叉积的性质求出。
多边形边上的格点数目可以枚举每条边求出。如果是水平或者垂直，显然可以得到，否则则是坐标差的最大公约数减1.(注这里是不计算端点的，端点必然在格点上，最后统计)
然后最后利用pick公式：多边形的面积=多边形边上的格点数目/2+多边形内部的格点数目-1。
#include<iostream>#include<fstream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<set>#include<map>#include<queue>#include<stack>#include<string>#include<vector>#include<sstream>#include<cassert>#define LL long long#define eps 1e-7#define inf 1<<30using namespace std;struct Point{ int x,y;}p[105];int n;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}int xmul(Point p0,Point p1,Point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int get_area(){ int area=0; for(int i=1;i<n-1;i++) area+=xmul(p[0],p[i],p[i+1]); return (area<0?-area:area);}int get_inedge(){ int ans=0; for(int i=0;i<n;i++){ int xx=abs(p[i].x-p[i+1].x); int yy=abs(p[i].y-p[i+1].y); if(xx==0&&yy==0) ans+=0; else if(xx==0) ans+=yy-1; else if(yy==0) ans+=xx-1; else ans+=gcd(xx,yy)-1; } return ans+n;}int main(){ int t,cas=0; scanf("%d",&t); while(t--){ scanf("%d",&n); p[0].x=0;p[0].y=0; for(int i=1;i<=n;i++){ int xx,yy; scanf("%d%d",&xx,&yy); p[i].x=p[i-1].x+xx; p[i].y=p[i-1].y+yy; } int area=get_area(); int edge=get_inedge(); int in=(area+2-edge)/2; printf("Scenario #%d:\n%d %d %.1f\n\n",++cas,in,edge,area/2.0); } return 0;}