POJ 1654 Area（任意多边形面积）
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：从一个点出发，8个方向，给出每一步的方向，求出走过的路径形成的多边形的面积。不过题目说了会首尾相接，而且不会有交叉，不过显然不一定是凸多边形。
http://poj.org/problem?id=1654
其实利用向量叉积求解多边形面积，也不只是适用于凸边形。出现凹的部分，刚好一正一负，抵消了。
不过这题讨厌的是精度。
double是不能过的，必须要用整数，又不能溢出，用64位整数，输出的时候面积只需要除以2，所以只需要判断奇偶。。。。。啊啊啊WA好多次不只因为精度，八个方向对应的坐标变化错了好几次，东西不分啊
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<string>#include<algorithm>#include<queue>#define LL __int64#define eps 1e-7#define N 2000000#define MOD 1000000007#define inf 1<<30#define zero(a) (fabs((double)(a))<eps)using namespace std;struct Point{ int x,y;}p[1000005];int n;int way[9][2]={1,-1,1,0,1,1,0,-1,0,0,0,1,-1,-1,-1,0,-1,1};LL xmul(Point p0,Point p1,Point p2){ return (LL)(p1.x-p0.x)*(p2.y-p0.y)-(LL)(p2.x-p0.x)*(p1.y-p0.y);}LL area(){ LL ans=0; for(int i=1;i<=n;i++) ans+=xmul(p[0],p[i],p[i+1]); return ans<0?-ans:ans;}char str[1000005];int main(){ int t; scanf("%d",&t); while(t--){ scanf("%s",str); p[0].x=0;p[0].y=0; for(n=0;str[n+1];n++){ int dir=str[n]-'1'; p[n+1].x=p[n].x+way[dir][0]; p[n+1].y=p[n].y+way[dir][1]; } LL ans=area(); if(ans%2==0) printf("%I64d\n",ans/2); else printf("%I64d.5\n",ans/2); } return 0;}