专栏首页用户6093955的专栏【改革春风吹满地 HDU - 2036 】【计算几何-----利用叉积计算多边形的面积】

【改革春风吹满地 HDU - 2036 】【计算几何-----利用叉积计算多边形的面积】

利用叉积计算多边形的面积

我们都知道计算三角形的面积时可以用两个邻边对应向量积(叉积)的绝对值的一半表示,那么同样,对于多边形,我们可以以多边形上的一个点为源点,作过该点并且过多边形其他点中的某一个的多条射线,这样就可以把该多边形变为多个三角形,然后利用叉积求面积即可。 不过要注意,对于三角形可以简单的用叉积的绝对值的一半表示,但对于多边形不可随意将它分割成的几个三角形对应的叉积的绝对值相加,要有一定顺序才可。 对于三角形,有

【该图片来源:https://www.cnblogs.com/xiexinxinlove/p/3708147.html】 对于多边形,若顶点是按逆时针方向排列的则方向为最终的值为正,反之为负。这里的排列方向是指你遍历其他顶点时相对于源点的走向。下面见HDU - 2036 题解。 补充:关于凸多边形和凹多边形的的样子见下图。

【该图片来源:https://www.cnblogs.com/xiexinxinlove/p/3708147.html

以上内容参考博文:https://www.cnblogs.com/xiexinxinlove/p/3708147.html

AC代码

该题目不用多讲,直接上代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn = 100 + 10;
struct Point
{
    int _x, _y;
    Point operator-(Point b)
    {
        Point a;
        a._x = _x - b._x;
        a._y = _y - b._y;
        return a;
    }
};
int n;
Point p[maxn];
int Cross(Point a, Point b)
{
    return a._x * b._y - a._y * b._x;
}
int Area(Point *p)
{
    int ans = 0;
    for(int i = 1; i < n - 1; i++)
        ans += Cross(p[i]-p[0], p[i+1]-p[0]);          //最好写成这样,清晰些,不容易出错
    return ans;     //题目说的逆时针,故ans为正值,直接返回即可
}
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(cin >> n && n)
    {
        for(int i = 0; i < n; i++)
            cin >> p[i]._x >> p[i]._y;
        int area = Area(p);
        printf("%.1lf\n", (double)area / 2.0);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-4544 湫湫系列故事——消灭兔子 (贪心+优先队列)

    将兔子的血量从大到小排列,将箭的属性写在类中(结构体也成),排序按照伤害从大到小排列,若有相等的则按价格从小到大排。

    _DIY
  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • Less Coin Tosses(Gym - 102346L)【打表+找规律】

    1.题意说的是给定你n位的二进制串,除了成对的(就是指那些1的个数相同或0的个数相同的),那些不成对的数有几个。比如n为3时,可以有000,001,010,01...

    _DIY
  • 旋转不变的感知哈希

    package com.imageretrieval.features; import com.imageretrieval.utils.ImageUtil;...

    Venyo
  • 零基础学贪心算法

    本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上...

    Angel_Kitty
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty
  • 暑假(补)-6

    优先队列是什么呢?优先队列其实是一种特殊的队列,对队列的元素按照一定的先后顺序,队列自动排序,这就是优先队列。

    AngelNH
  • LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

    ShenduCC
  • 算法-快速排序

    瑞新
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051

扫码关注云+社区

领取腾讯云代金券