将树围起来(几何凸包)- HDU 1392

几何凸包:

在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。如下图所示。计算凸包也就是求得外围(蓝线上)的那些点

数学上有严格的证明,如下:

在一个实数向量空间V中,对于给定集合X,所有包含X的凸集的交集S被称为X凸包

凸包的算法可以算是计算几何中最基础的算法之一了。寻找凸包的算法有很多种,Graham算法是一种十分简单高效的二维凸包算法,能够在O(nlogn)的时间内找到凸包。

寻找凸包算法涉及到向量的叉乘,上一篇几何文章提到了,可以再复习下。如下图:

Problem Description

There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him? The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line. 森林里有很多树,一个农夫想买条绳子将这些树围起来,但是他需要知道绳子的最小长度。他不知道怎样计算,请你帮忙。树的直径忽略不计,可以认为是一个点,绳子的厚度也不计,可以认为只是简单的线段。

There are no more than 100 trees.

不会超过100棵树。

Input

The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank. 多组测试,每个测试第一行是树的数目N,接着N行是树的坐标。 Zero at line for number of trees terminates the input for your program.

N=0表示结束。

Output

The minimal length of the rope. The precision should be 10^-2.

精确到小数点2位。

Sample Input

9 
12 7 
24 9 
30 5 
41 9 
80 7 
50 87 
22 9 
45 1 
50 7 
0

Sample Output

243.06

这是一个计算几何凸包的题目,直接用凸包算法计算即可。

解题思路:

Andrew算法,Graham算法的变种,速度更快稳定性也更好。

1)把P1,P2放入凸包中,凸包中的点使用栈存储,一般的我们取最左边(横坐标最小)的点作为参考点 如果有多个这样的点就取最下面的(纵坐标最小)。

2)从p3开始,当下一个点在凸包当前前进方向(即直线p1p2)左边的时候继续。

3)否则依次删除最近加入凸包的点,直到新点在左边。

源代码:G++

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;

//定义一个点类型
struct Point {
    LL x, y;

    Point() {}
    Point(LL _x , LL _y): x(_x), y(_y) {}

    //重载减法运算
    Point operator - (const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
};

//所有的点
Point points[110];
Point ch[110];

//计算叉积
LL Cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

bool cmp(const Point &a, const Point &b) {
    return (a.x < b.x || (a.x == b.x && a.y < b.y));
}

//Andrew算法,Graham算法的变种,速度更快稳定性也更好。
int Andrew(int size) {
    //1.把所有点按照x从小到大进行排序 (x同则y用y进行排序)
    sort(points, points + size, cmp);

    int m = 0;
    //直到碰到最右边的Pn,求出下凸包即凸包的下轮廓
    for (int i = 0; i < size; i++) {
        //如果叉积小于0,表示p0p2在p0p1的左方向
        while (m >= 2 && Cross(ch[m - 1] - ch[m - 2], points[i] - ch[m - 2]) < 0)
            m--;

        ch[m++] = points[i];
    }

    int k = m;
    //从Pn反过来重复该步骤求出上凸包,合并起来后就是完整的凸包
    for (int i = size - 2; i >= 0; i--) {
        while (m > k && Cross(ch[m - 1] - ch[m - 2], points[i] - ch[m - 2]) < 0) 
            m--;

        ch[m++] = points[i];
    }

    return m;
}

double distance(const Point &a, const Point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
    //freopen("test.txt", "r", stdin);
    //输入有多少个点size
    int size = 0;
    while (~scanf("%d", &size) && size) {
        //依次输入这n个点的坐标
        for (int i = 0; i < size; i++){
            scanf("%lld%lld", &points[i].x, &points[i].y);
        }

        //如果只有2个点,直接输出距离
        if (size == 2) {
            printf("%.2f\n", distance(points[0], points[1]));
            continue;
        }

        int cnt = Andrew(size);

        //将第cnt个设置为第一个点,也就是最后一个点和第一个点连起来的距离
        ch[cnt] = ch[0];

        //总距离
        double sum = 0;

        //依次累计每个点的距离
        for (int i = 0; i < cnt; i++)
            sum += distance(ch[i], ch[i + 1]);

        printf("%.2f\n", sum);
    }
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-05-17

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

Tensor

  在 TensorFlow 中用 tensor 数据结构来代表所有的数据, 计算图中, 操作间传递的数据都是 tensor。

16720
来自专栏小鹏的专栏

tf API 研读2:math

TF API数学计算 tf...... :math (1)刚开始先给一个运行实例。         tf是基于图(Graph)的计算系统。而图的节点则是由操作(...

81550
来自专栏前端新视界

使用 JS 输出螺旋矩阵

这是我曾经遇到过的面试题,在 LeetCode 上找到了题目的原型,难度中等。题目描述如下:

14020
来自专栏小小挖掘机

大过年的,一起来用Seq2Seq来作对联吧!

Seq2Seq全称Sequence to Sequence,在机器翻译、文章摘要等领域有着广泛的应用。其本身很简单,是一个如下图所示的Encoder-Decod...

1.3K80
来自专栏Python小屋

Python+numpy实现函数向量化

Python本身对向量操作的支持并不是很好,需要借助列表推导式或函数式编程来实现,例如: >>> import random # 生成随机测试数据 >>> x...

85850
来自专栏技术专栏

Python3入门机器学习(二)- Jupyter Notebook与Numpy的使用

测试结果表明,运行了一千次,取有价值的7次,平均每次耗时324+/-5.7 μs(有多少次循环是由Jupyter Notebook自动决定的)

39630
来自专栏和蔼的张星的图像处理专栏

730. 所有子集的和递归

给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和 样例

14620
来自专栏窗户

有限域(2)——理想和商环

  我们上一节介绍了环(ring)、域(field)的概念,并给了一些环、域的实例。比如我们知道整数环、方阵环、有理数域、实数域等。我们知道,域是环的一个种。最...

9220
来自专栏机器学习算法与Python学习

Python: numpy总结(3)

21、dot矩阵点积 例子: ll = [[1,2,3],[4,5,6],[7,8,9]]ld = dot(ll,ll) print 'dot:',l...

34340
来自专栏机器学习从入门到成神

稀疏矩阵转置

矩阵是线性代数中的一个知识,刚开始学习的时候可能感觉不到它有什么用处,最初的感觉就是对二维数据的操作。其实现实生活中矩阵的用处太大了,设计领域相当的广泛。在此只...

26610

扫码关注云+社区

领取腾讯云代金券