POJ 1654 Area(多边形面积)

POJ 1654 Area(多边形面积)

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

题意:

在一个网格中,你当前在起始点,然后给你一些数字,每个数字表示你网当前位置的8个方向走一步.然后你到了下一个网格点了,就这样让你走出一个多边形,要你输出该多边形的面积. 题目保证最后一步是回到原点,且保证能形成多边形.

分析:

82 6 4 : 上,下,右,左. 9 7 3 1 : 右上,左上,右下,左下. 数字5不用处理直接忽略.

我们只要根据起点位置和接下来的一系列操作算出后续的所有点坐标即可. 然后用多边形面积函数去计算.

注意:由于所有点都是整点,且根据题意最终的面积一定是0.5的整数倍(因为半个正方形面积是0.5),所以我们用long long保存多边形面积的两倍. 最终除以2即可.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point
{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x, A.y-B.y);
}
long long Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}

long long PolygonArea(Point *p,int n)//返回多边形面积的双倍
{
    long long area=0;
    for(int i=1;i<n-1;++i)
        area += Cross(p[i]-p[0],p[i+1]-p[0]);
    return area<0?-area:area;
}

const int dx[]={0,-1,0,1,-1,0,1,-1,0,1};//
const int dy[]={0,-1,-1,-1,0,0,0,1,1,1};
const int maxn=1000000+5;
char str[maxn];
Point p[maxn];
int n;
int main()
{
    int T; scanf("%d%*c",&T);
    while(T--)
    {
        n=0;
        p[0]=Point(0,0);
        scanf("%s",str);
        n=strlen(str)-1;
        for(int i=0;i<n-1;++i)
            p[i+1]=Point(p[i].x+dx[str[i]-'0'], p[i].y+dy[str[i]-'0']);
        long long ans=PolygonArea(p,n);
        if(ans%2==0)printf("%I64d\n",ans/2);
        else printf("%I64d.5\n",ans/2);
    }
    return 0;
}