POJ 1654 Area 解题报告

时间：2010-05-13 来源：MC_ACM

Description

You are going to compute the area of a special kind of polygon. One vertex of the polygon is the origin of the orthogonal coordinate system. From this vertex, you may go step by step to the following vertexes of the polygon until back to the initial vertex. For each step you may go North, West, South or East with step length of 1 unit, or go Northwest, Northeast, Southwest or Southeast with step length of square root of 2.For example, this is a legal polygon to be computed and its area is 2.5:

Input

The first line of input is an integer t (1 <= t <= 20), the number of the test polygons. Each of the following lines contains a string composed of digits 1-9 describing how the polygon is formed by walking from the origin. Here 8, 2, 6 and 4 represent North, South, East and West, while 9, 7, 3 and 1 denote Northeast, Northwest, Southeast and Southwest respectively. Number 5 only appears at the end of the sequence indicating the stop of walking. You may assume that the input polygon is valid which means that the endpoint is always the start point and the sides of the polygon are not cross to each other.Each line may contain up to 1000000 digits.

Output For each polygon, print its area on a single line.

Sample Input

825

6725

6244865

Sample Output

0.5

这个题就是像手机玩游戏一样的按键，1:左上2:上3:右上4:左6:右7:左下8:下9:右下

题目大意是让你求出它所围成的面积，一行中最多可以有1000000数字，因此要用到__int64

每行的最后为５，而且假设了一定能够回到原点，而且边不会相交。

采用面积累加的方法，每相邻的两个点和原点构成三角形，不断的累加面积。

还有要注意的是最后的输出。如果用double输出的话，通过不了，因此我们先判断是不是奇数，如果是奇数的话，则我们除以二的时候认为填上".5"　。最后时间用了219ms。听说如果用gets()的话会更快。

#include<iostream>
using namespace std;
__int64 dic[10][2]={{0,0},{1,-1},{1,0},{1,1},{0,-1},{0,0},{0,1},{-1,-1},{-1,0},{-1,1}};
__int64 Get2Area(__int64 x1,__int64 y1,__int64 x2,__int64 y2)//知道两个点和原点。

{
    return (x1*y2-x2*y1); //求三角形面积

}
int main()
{
    int n,p;char c;
    __int64 x1=0,x2=0,y1,y2,area=0; //这个题必须用__int64，discuss中说用long long过不了

    cin>>n;
    while(n--)
    {
        while((c=cin.get())!='5') //标准输入流的提取

        {
            p=c-'0';
            x2=x1+dic[p][0];
            y2=y1+dic[p][1];
            area+=Get2Area(x1,y1,x2,y2); //面积累加

            x1=x2;
            y1=y2;
        }
        if(area<0)area=(-1)*area;
        x2=area/2; //废物利用嘛，省空间。　　

        if(area!=x2*2){printf("%I64d.5\n",x2);} //用cout不行，必须用printf(),如果用double精度有问题

        else{("%I64d\n",x2);}
        area=0;
    }
    return 0;
}

PS:已知三角形两个顶点，另一个点为原点，求面积。