[原创]POJ 1654 Area 【叉乘+外积的几何意义】【计算几何】

2016-04-01 13:54:06 Tabris_ 阅读数：795

博客爬取于2020-06-14 22:44:43
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51036352

题目链接—> 点此传送阵

Area
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17766 Accepted: 4925
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

4
5
825
6725
6244865
Sample Output

0
0
0.5
2

题目大意: 有一个直角坐标系 初始位置在（0,0） 给你一个字符串，其中1,2,3,4,6,7,8,9分别对应向8个方向 最后走回来 确保 数据最后能走回原点 问行走路线所圈成的多边形面积。。

最开是就想到了要用外积的几何意义来做 但是题目不能确保所走过的路线能是一个凸包 所以不敢用 然后就一直没有别的思路 最后按照样例 画了画 发现 外积的几何意义成立 于是有画了个凹包 发现也成立 于是敲了敲代码 就Ac了。。

外积的几何意义：
外积也称叉积或向量积
几何意义就是两个向量所构成的平行四边形面积就是外积
三角形的话就是外积的一半

这里写图片描述

如上图所示
Sabcd=αxβ；
SΔabc=αxβ；

本题就是把除原点外的相邻两个点与原点组成的三角形的面积加和就行

用外积求面积是会遇到结果为负的情况 是正常的 ，这样最后得到的和就会把多加上去的消掉 ，
注意 最终结果为正
注意 double的精度不好控制 用long long int 比较好控制

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cstdlib>
# include <string>
using namespace std;

struct point
{
    int x,y;
} p[1000005],temp;

long long int mul(point p1,point p2,point p0)
{
    return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}

point pp(char a,point b)
{
         if(a=='1') b.x--,b.y--;
    else if(a=='2') b.y--;
    else if(a=='3') b.x++,b.y--;
    else if(a=='4') b.x--;
    else if(a=='5') ;
    else if(a=='6') b.x++;
    else if(a=='7') b.x--,b.y++;
    else if(a=='8') b.y++;
    else if(a=='9') b.x++,b.y++;

    return b;
}
char a[1000005];
int main()
{
    int  t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        gets(a);
        int l=strlen(a);
        if(l <= 3){
            printf("0\n"); continue;
        }
        p[0].x=0,p[0].y=0;

        for(int i=1; i<l; i++)
        {
            p[i]=pp(a[i-1],p[i-1]);
        }
        long long int area=0;
        for(int i=2;i<l;i++)
        {
           long long int  aa=mul(p[i-1],p[i],p[0]);
            printf("-->%I64d\n",aa);
            area+=aa;
        }
        if(area<0) area=-area;
        if(area%2==0)  //这里只是用来控制精度
        printf("%I64d\n",area/2);
        else
            printf("%I64d.5\n",area/2);
    }
    return 0;
}