POJ 1654 area 解题

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

Sample Output

分析：

有十多次WE,经过查看别人的代码，原来是如果用double 表示总面积会有精度问题，所以需要用__int64或者long long int 来表示总面积，用int也不行，据题可知，最多走动变换1000000次，如果是正方形，每个边250000，总面积*2=125 000 000 000，远远大于int的表示范围，而double类型，虽然表示范围广，但是有漏数字的情况，例如可能发生不能表示64000001，即使可以表示64000000和64000002，。

总面积用叉积法求解。

#include <stdio.h>

typedef struct{

    int x,y; //此处__int64和int都可以。

} Point;

int dx[]={0,-1,0,1,-1,0,1,-1,0,1}; //此处用查表的方式，比用switch好用多了。

int dy[]={0,-1,-1,-1,0,0,0,1,1,1};

char line[1000010];

void handle(){

    int i,j,n;

    long long area=0;

    Point p1={0};

    Point p2={0};

    scanf("%s",line);

    n=strlen(line);

    for(i=0; i<n-1; i++){

        p2.y+=dy[line[i]-'0'];

        p2.x+=dx[line[i]-'0'];

        area+= p2.x*p1.y-p2.y*p1.x;

        p1.y=p2.y;

        p1.x=p2.x;

    }

    area=area<0?-area:area;

    if(area%2 == 0){ //如果解是偶数，就不用输出.5

        printf("%I64d\n",area/2); //输出必须采用I64d的方式，否则也会WE

    }else{

        printf("%I64d.5\n",area/2);

    }

}

int main(){

    int c,i,j;

    scanf("%d",&c);

    for(i=0;i<c;i++){

        handle();

    }

}

巴特西

POJ 1654 area 解题

最新文章

热门文章