August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
10
｜
第
1
章
3.
以
{
P
n-
2
,
low
,
P
0
}
这个顺序组成的点集为基础，在剩余的点中选择可以组成凸包的
点——从
P
1
开始，将每个点尝试加至这个点集的尾部，如果这个点集的最后三个点
组成的两条线段向左拐，那么就需要移除这个错误的点。
4.
在访问完所有的点之后，就得到了一个凸包，如图
1-3
所示。
图 1-3：使用贪心算法得到的凸包
1.3.2 分治算法
我们也可以将点按
x
坐标从左到右排序（如果
x
坐标相同，就按照
y
坐标排序），就能
将这个问题分成两个稍微小一点的子问题。首先可以从点
p
0
到
p
n
-1
，按照从左到右、顺
时针的顺序计算出一个上半部分凸包，然后用同样的方法从
p
n
-1
到
p
0
，按照从右到左、
同样是顺时针的顺序计算出下半部分凸包。
凸包扫描算法
（将在第
9
章中介绍）可以计
算出这些半凸包（见图
1-4
），然后将结果合并在一起生成最终的凸包。
上半部分凸包 ူӷևݴཫԈ
图 1-4：合并上、下部分凸包组成完整凸包
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.