poj 1654 Area（神题）

柔情只为你懂 2023-08-17 16:03 108阅读 0赞

> 题目衔接：[http://poj.org/problem?id=1654][http_poj.org_problem_id_1654]

> <table> 
>  <tbody> 
>   <tr> 
>    <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
>    <td>&nbsp;</td> 
>    <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
>   </tr> 
>   <tr> 
>    <td><strong>Total Submissions:</strong>&nbsp;22770</td> 
>    <td>&nbsp;</td> 
>    <td><strong>Accepted:</strong>&nbsp;6146</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 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:
> 
> ![format_png][]
> 
> 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
> 
>     4
>     5
>     825
>     6725
>     6244865
> 
> Sample Output
> 
>     0
>     0
>     0.5
>     2
> 
> Source

>  题目大意：给你一个字符串，串表示的是对于这个点的操作，如何操作自行看题，然后保证这些点能组成一个四边形，问你最后这个四边形的面积是多少
> 
> 思路：题意如此简单，坑点却是一个比一个多，果然计算几何的题能1A的题都基本不存在，这个题要注意的有：
> 
> 1.内存问题：如果要存点，必须用整数不能用double存否则会爆内存
> 
> 2.注意要用long long 不能用double这个是不行的，
> 
> 3.如果是存点最后计算面积，我们可能马上想到的是叉积计算，如果这样算我们不能提前取绝对值，不然会wa到吐（例如样例：862688444226 正确答案是5
> 
> 4.由于答案最后既有整数也有小数，所以我们在计算的时候要用整数存，不能用double或者float，最后还需要判断能否整除
> 
> 坑点大概就这么些

代码：

/*
    题目大意：给你一个字符串，代表走的方向，从原点开始走，问你最后的面积是多少，5代表结束前进
    题目保证这个图形是能够合并的
    
    思路：按照他所给的方式走下去，直接得出答案
    */
    #include<set>
    #include<map>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define inf 0x3f3f3f
    #define bug  printf("bug\n")
    const int maxn=1e6+10;
    const double pi=acos(-1.0);
    const double esp=1e-6;
    const int N=2e2+10;
    struct point
    {
        int x,y;
    };
    point p[maxn];
    int cmult(point a,point b,point c)///叉积
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    char s[maxn];
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%s",s);
            int l=strlen(s);
            int cnt=1;
            p[0].x=0,p[0].y=0;
            for(int i=0;i<l;i++)
            {
                if(s[i]=='5')
                    break;
                else
                {
                    if(s[i]=='8')
                    {
                        p[cnt].x=p[cnt-1].x;
                        p[cnt].y=p[cnt-1].y+1;
                    }
                    else if(s[i]=='2')
                    {
                        p[cnt].x=p[cnt-1].x;
                        p[cnt].y=p[cnt-1].y-1;
                    }
                   else if(s[i]=='6')
                    {
                        p[cnt].x=p[cnt-1].x+1;
                        p[cnt].y=p[cnt-1].y;
                    }
                    else if(s[i]=='4')
                    {
                        p[cnt].x=p[cnt-1].x-1;
                        p[cnt].y=p[cnt-1].y;
                    }
                    else if(s[i]=='9')
                    {
                        p[cnt].x=p[cnt-1].x+1;
                        p[cnt].y=p[cnt-1].y+1;
                    }
                    else if(s[i]=='7')
                    {
                        p[cnt].x=p[cnt-1].x-1;
                        p[cnt].y=p[cnt-1].y+1;
                    }
                    else if(s[i]=='3')
                    {
                        p[cnt].x=p[cnt-1].x+1;
                        p[cnt].y=p[cnt-1].y-1;
                    }
                    else if(s[i]=='1')
                    {
                        p[cnt].x=p[cnt-1].x-1;
                        p[cnt].y=p[cnt-1].y-1;
                    }
                    cnt++;
                }
            }
            ll ans=0;
            for(int i=1;i<cnt-2;i++)
            {
                ans+=(cmult(p[0],p[i],p[i+1]));
            }
            ll ss=(ll)fabs(ans);
            if(ss%2==0)
                printf("%lld\n",ss/2);
            else
                printf("%lld.5\n",ss/2);
        }
        return 0;
    }

[http_poj.org_problem_id_1654]: http://poj.org/problem?id=1654
[format_png]: /images/20230810/f37c9b59df894d39ba9bbab9ed7cb689.png