POJ 1654 Area解题报告

一、问题描述

二、解题思路

使用叉积求面积。假设起点为(0,0)，可以将多边形分成多个三角形，分别求三角形的面积，不断进行累加。因为三角形的面积可能会出现0.5的情况，因此先用叉积计算矩形面积，即是三角形面积的两倍，最后再将结果除以2。

三、代码

 

#include<iostream>
using namespace std;
struct Point
{
    __int64 x;
    __int64 y;
};
int D[10][2]={{0,0},{-1,-1},{0,-1},{1,-1},{-1,0},{0,0},{1,0},{-1,1},{0,1},{1,1}};
//求面积
__int64 area(Point p1,Point p2)
{
    return p1.x*p2.y-p2.x*p1.y;
}
int t;
char ch[1000005];
int main()
{
    int i,j;
    int id;
    int len;
    __int64 Area=0;
    scanf("%d",&t);
    Point p0,p1;
    for(i=0;i<t;++i)
    {
        p0.x=0;
        p0.y=0;
        Area=0;
        scanf("%s",&ch);
        len=strlen(ch);
        for(j=0;j<len-1;++j)
        {
            id=ch[j]-'0';
            p1.x=p0.x+D[id][0];
            p1.y=p0.y+D[id][1];
            Area+=area(p1,p0);
            p0=p1;
        }
        if(Area<0)
            Area=-Area;
        __int64 res=Area/2;
        if(res*2 == Area)
            printf("%I64d\n",res);
        else
            printf("%I64d.5\n",res);
    }
    return 0;
}