
不管对初出茅庐的新人还是身经百战的老手,用“挑战”一词形容程序设计竞赛是再合适不过的了。酷爱编程的人们往往喜欢挑战,但大多数程序员对各种程序设计竞赛却是“敬而远之”,为什么会这样呢?原因在于,学习编程语言和软件开发的知识只是接受这些挑战的必要而非充分条件。要想在程序设计竞赛中脱颖而出,还需要更多的知识和技能。而这些知识和技能,却是很难在传统的课堂和教科书中学到的。
本书的目标读者便是那些已经具备初步的编程技能,对程序设计竞赛充满好奇,希望有机会武装自己、接受编程挑战的人,以及他们的老师和教练(甚至父母)。即使不参加任何竞赛,从本书的编程挑战中学到的东西,也会对程序员的职业生涯产生重要影响,更不用说这些挑战本身就是充满乐趣、引人入胜的。
本书文字精练、通俗易懂。尽管每一章都涉及一个不同的领域,但篇幅却短得甚至可以一口气读完。另外,所有题目均附有难度、流行度等客观评价系数,并可以在线提交。写出程序并不意味着完善的解决了难题,只有通过了评测系统的严格把关才能让人信服。
计算机编程能给人带来很多特殊的快乐。
付出总会有回报,亲手做出一个有用的东西并看着它成功运转时,你为之满足;
灵光一现,于是轻松解决一个困扰你多年的问题时,你为之兴奋;
对美的执着追求能让一名普通黑客成为艺术家,而吝啬已然成为了一种美德,
尤其是从那些经过锤炼后的精巧算法和简洁代码中榨取最后一滴``性能之油''。
国际编程竞赛题目中的游戏、谜题和挑战是体验这些快乐的绝佳途径,同时还能提高你的算法能力和编程技巧。
%such as the
%ACM International Collegiate Programming Contest
%and the International Olympiad in Informatics
本书包含了百余个历届比赛中出现的题目,并讨论了解决这些题目所需的理论和思维方式。
读者可以在两个在线评测系统中提交其中任何一道题目的程序,并获得即时的自动评分。
若能将评测系统和本书有机结合,你会亲身体会到:迎接挑战和提升编程水平是一件多么新奇、刺激的事啊!
本书可用于自学、讲授算法、编程类创新课程以及比赛的训练。
\subsection*{致读者}
本书中的题目选自Valladolid大学在线评测系统({\it
http://uva.onlinejudge.org/})中的上千道编程题目。
\review{找找新数据噢} 到目前为止,该系统已经评测了来自27
000个注册用户的超过一百万份提交。
我们只选择了精品中的精品,即那些最好玩、最刺激和最有意思的题目。
我们把这些题目分成若干个类别,然后提供了足够的教学材料(主要是数学和算法)来帮助你解决它们。
书中配备了很多参考程序来更好地讲解重要的概念。阅读本书并尝试解决这些题目,
你会对回溯法、动态规划等算法技巧以及数论、计算几何等高级话题有更加具体和深刻的理解。
即使不参加编程竞赛,关注这些东西也是十分有益的。
%Beyond their educational value, these problems are suggestive of the
%interview `puzzle' problems most advanced companies
%give all new job applicants.
%You can see them now, or you can see them later.
%We annotate each problem as to difficulty,
%and provide hints for certain problems in case you get stuck.
%However, we encourage you to try each problem first before peeking at the hint.
%Our goal is to help as many people as possible take advantage of this
%unique educational resource.
\review{fun和interesting的区别...}
多数题目都很生动。它们展示了计算机科学和数学中令人着迷的话题,有时还会以搞笑故事的面目出现。
它们往往涉及一些有意思的领域来深入学习研究,因此在合适的时候,我们总是给出注解和进一步的阅读材料。
%Although the problem statements are all available on line, they are
%not organized by topics as in this book. Further, we find it much
%easier to browse through a printed book than face international
%transmission delays each time we want to turn the page.
我们发现,主要接受项目开发和软件工程方面训练的人们通常忽视了算法的重要性。
类似地,理论派算法研究者往往低估了把算法转化为程序的难度,也不清楚编程智慧如何化繁为简。
基于上述原因,本书的第一个部分主要关注编程技巧,包括数据类型和库函数的合理运用。
这些是书中第二部分那些以算法为主线,
难度更大章节的基础。要想成为一名全能的问题求解大师,必须同时精通这两个部分。
\subsection*{致教师}
本书被设计为以下三种类型的课程教材:\vspace{0.15mm}
\begin{itemize}
\item 偏重编程的算法课程。\vspace{0.15mm}
\item 偏重算法的编程课程。\vspace{0.15mm}
\item 训练学生参加 ACM/ICPC(ACM 国际大学生程序设计竞赛) 或
IOI(国际信息学奥林匹克)的选修课。\vspace{0.15mm}
\end{itemize}
这样的课程对所有相关人士来说都是愉快的。\vspace{0.15mm}
学生的潜能很容易被比赛本身的刺激所激发,\vspace{0.15mm}并且每次提交通过一道题目时都将得到增强。
最直白的程序可能会被测试系统返回``超时''信息,\vspace{0.15mm}于是学生会很自然地寻找更有效的解法。
正确的洞察力会让一个十余行的小程序取代一大片杂乱无章的代码。\vspace{0.15mm}最优秀的学生甚至自愿尝试更多的题目来获得快感。
讲授这样的课程也是愉快的。很多题目十分精巧,\vspace{0.15mm}尽管在算法和编程本质上并无特殊之处,但题目却令人耳目一新。
对于这样的问题,要找到最佳解法需要洞察力和灵感。\vspace{0.15mm}寻找这些题目的解法是令人兴奋的,
而当我们所教的学生独立找到解法时,我们会更加兴奋。\vspace{0.15mm}
从教育学的角度讲,本书的特点包括:\vspace{0.15mm}
\begin{itemize}
%\newitem{New Motivations for Traditional Algorithmics}
\item{\kaishu 作为标准算法教材的补充}------
尽管本书体系完整,写作时仍然考虑到大多数学生已有了一些算法基础。\vspace{0.15mm}
本书是作为传统算法课程的补充教材来设计(与定价)的,\vspace{0.15mm}它用具体实现补充抽象描述,
用实践经验补充理论体系。另外,\vspace{0.15mm}它还涉及一些多数标准教材中都没有提到的有趣主题。\vspace{0.15mm}
%(e.g., backtracking, number theory, and computational geometry)
\item{\kaishu 提供经典算法的完整实现}------
很多学生在把抽象的算法描述转化成能正确运行的代码时困难重重。\vspace{0.15mm}
为了帮助他们,我们精心编写了书中所讨论的所有重要算法的程序。\vspace{0.15mm}这些程序只用到~C~语言的一个子集,
因此~C++~和~Java~程序员也能轻易看懂。\vspace{0.15mm}
书中的不少习题都只需适当修改这些例程即可解决,\vspace{0.15mm}从而为初学者提供了一条宽敞的入门之路。\vspace{0.15mm}
\item{\kaishu 内置课程管理系统}------
我们已经打造了一个特别的课程管理系统,\vspace{0.15mm}使得管理一门这样的课程易如反掌。
所有测试和评分都是自动进行的,\vspace{0.15mm}你完全不必操心!
用我们的网站 \oururl\
可以轻松管理花名册、布置作业、查看学生的程序和分数,\vspace{0.15mm}甚至还能检测到疑似作业!
%However, our experience suggests that the competitive challenge of
%such courses minimizes problematic behavior.
\item{\kaishu 帮助程度参差不齐的学生}------
本书在题目选择时有意覆盖了一个较宽的难度范围。\vspace{0.15mm}多数题目适合初学者,而其他题目即使对于备战国际竞赛的选手来说也是富有挑战的。
我们为多数题目提供了解题提示。\vspace{0.15mm}
为了帮助学生挑选适合自己的题目,我们给每道题目标注了三种类型的难度值。
题目的 {\em 流行度} (A, B, 或 C) 是指有多少人提交过此题,而{\em
成功率}(low~表示低,high~表示高)是指这些人中正确解决此题的比率。
最后,题目的{\em 等级} (从1 到
4,大致表示从新手到高水平读者)表示解题者应具有的水平等级。
\end{itemize}
\swallow{ Have each student register at the online judge, and mail
you their assigned ID number. Plugging this ID (say 8826) into the
AuthorInfo file
\url{http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:8826} gives
you a link to the student's complete record. After building a web
page with all these links, class performance can be monitored
simply by clicking through the links. Sufficiently paranoid
instructors may wish to collect solutions and run them through
plagiarism detection programs such as Moss (see
\url{http://www.cs.berkeley.edu/$\sim$aiken/moss.html}), since the
judge isn't checking. However, our experience suggests the
competitive challenge aspect of such courses minimizes such
problems. }
\secondedition{ \question{Can you set up a special course
management WWW page for instructors to make it even easier for
them (e.g. do cheat checking, impose calendar deadlines, and let
the instructor view the student's solutions)? Let's talk about
this.} }
\subsection*{致竞赛选手与教练}
本书尤其适合作为高中和大学的编程竞赛培训材料。
我们为数学和算法中的重要主题提供方便的总结和参考,还配备了合适的挑战题目来帮助你掌握这些内容。
自动评测系统像ACM/ICPC中的真人裁判一样检查所提交程序的正确性。只要你拥有该系统的个人账号,
你就可以提交~C、C++、Pascal或Java~程序,然后等待系统告诉你这个程序是对还是错。
系统还会为你保存一份统计信息,让你有机会与成千上万的其他用户进行对比。
为了帮助竞赛选手,我们请到了三个重要编程比赛------ACM国际大学生程序设计竞赛(ICPC)、
国际信息学奥林匹克(IOI)、TopCoder编程挑战赛------的决赛选手分享经验,并把这些成功的秘密写在附录中。
我们还介绍了这三项赛事的历史和参赛方法,最大限度地帮助你施展才华。
\review{过期否} 大约有80\%
的~ACM/ICPC~决赛选手用~Valladolid~在线评测系统进行训练。
ICPC~全球总决赛常常在夏威夷这样令人神往的异国他乡举行,这无疑为选手们提供了额外的精神动力。加油吧!
\subsection*{相关网站}
本书有两个配套网站。书中的所有题目均可在 \oururl\,\linebreak
提交,该网站还提供了一些辅助材料,
包括书中所有程序的电子版以及帮助教师们把书中的材料融入课堂的课程笔记。
本书中的所有题目(以及很多其他题目)也可以在~Valladolid~大学在线评测系统
{\it http://}\linebreak{\it uva.onlinejudge.org/}
中提交。书中的所有习题均同时标注两个评测系统的ID号,供读者\linebreak
选择。
\subsection*{致谢}
本书的成书在很大程度上归功于那些欣然授权把他们设计的竞赛题目用在本书和在线评测系统中的人们。
本书中的题目由来自四大洲的至少17位命题者提供,尤其是Gordon
Cormack和Shahriar Manzoor, 就好比Sam Loyd和H. E.
Dudeney$^1$\footnotetext{\
\footnotesize\zihao{6}$^1$译者注:两位都以提出了大量有趣但富有挑战性的数学谜题而著称。}一样!
作者和题目的完整列表见附录,但我们要在这里特别感谢如下的竞赛组织者:
Gordon Cormack (38题), Shahriar Manzoor (28), Miguel
Revilla (10), Pedro Demasi (8), Manuel Carro (4),
Rujia Liu(刘汝佳) (4), Petko Minkov (4), Owen Astrakan (3),
Alexander Denisjuk (3), Long Chong(龙翀) (2), Ralf Engels (2),
Alex Gevak (1), Walter Guttmann (1), Arun Kishore (1), Erick
Moreno (1), Udvranto Patik (1) 以及 Marcin
Wojciechowski (1)。
其中的部分题目由第三方设计,我们已在附录中向他们致谢。
其中一些题目的原作者已经难以考证。我们想尽办法找到每道题目的原作者,
并得到了能代表作者发言的人授权。如有疏漏,在敬请原谅的同时还希望能告知我们,以便在致谢中补充。
在线评测系统项目是许多人辛勤劳动的结晶。 Ciriaco Garc\'\i a
是评测系统软件的主要开发人员,也是项目的核心支持人员。
\review{that help the judge in a friendly manner到底是?} Fernando
P. N\'{a}jera 开发了一系列辅助工具,使得评测系统更加友好。 Carlos
M. Casas 维护测试数据,确保它们在正确的前提下既公平又严格。 Jos\'e
A. Caminero 和 Jes\'{u}s Pa\'{u}l
负责检查和完善题目描述,并测试参考程序。 我们还要特别感谢 Miguel
Revilla, Jr,他建立并维护着\oururl。
%\todo{Acknowledge all robot judge people and anyone else you think appropriate.}
本书曾作为Stony Brook~2002年春季学期的一门课程的教材。
该课程由Vinhthuy Phan和Pavel Sumazin任教,并修改了诸多错误。
我们今年很棒的两支参赛队伍的成员(Larry Mak, Dan Ports, Tom
Rothamel, Alexey Smirnov, Jeffrey Versoza和Charles Wright)
帮忙评阅了手稿,感谢他们的兴趣和反馈。 Haowen Zhang
仔细阅读了手稿,测试了书中的程序,并简化了代码,为本书的修改做出了重要贡献。
%\todo{Acknowledge all of the publisher's people.}
感谢Springer-Verlag的Wayne Yuhasz, Wayne Wheeler, Frank Ganz,
Lesley Poliner 和 Rich
Putter。没有他们的帮助,本书无法从手稿最终变成出版物。
我们还要感谢 Gordon Cormack, Lauren Cowles, David Gries, Joe
O'Rourke, Saurabh Sethia, Tom Verhoeff, Daniel Wright 和 Stan
Wagon。他们认真仔细的评阅极大地提高了最终成品的质量。 Fulbright
Foundation 和
Valladolid大学应用数学与计算系为两位作者面对面交流和一起工作提供了必要的支持。
Citigroup CIB,通过 Peter Remch 和 Debby Z. Beckman
所做出的努力,为Stony Brook大学的 ACM
ICPC产生了深远的影响。它的参与促成了本书的写作。
第1章 入门
{1}
{1.1 初识自动评测系统
{1}
1.1.1
评测系统反馈{1}
{1.2 挑选你的武器
{3}
1.2.1
程序设计语言{3}
1.2.2
如何阅读本书的程序{4}
1.2.3
标准输入输出{5}
{1.3 编程提示 {6}
{1.4
基本数据类型{8}
{1.5 关于习题{10}
{1.6 习题{11}
1.6.1 $3n+1$问题(3n+1
Problem){11}
1.6.2
扫雷(Minesweeper){12}
1.6.3 旅行(The
Trip){13}
1.6.4
液晶显示屏(LC-Display){14}
1.6.5 图形化编辑器(Graphical
Editor){15}
1.6.6
解释器(Interpreter){16}
1.6.7 将军(Check the
Check){17}
1.6.8 澳大利亚投票(Australian
Voting){19}
{1.7 提示{20}
{1.8 注解{20}
第2章 数据结构
{22}
{2.1 基本数据结构
{22}
2.1.1
栈{22}
2.1.2
队列{23}
2.1.3
字典{25}
2.1.4
优先队列{26}
2.1.5
集合{26}
{2.2 库函数 {27}
2.2.1
C++标准模板库{27}
{2.3 程序设计实例:纸牌大战
{28}
{2.4 准备行动 {29}
{2.5 字符串输入输出
{30}
{2.6 赢得战争 {32}
{2.7 测试与调试
{33}
{2.8 习题 {35}
2.8.1 快乐的跳跃者(Jolly
Jumper){35}
2.8.2 扑克牌型(Poker
Hands){35}
2.8.3
罢工(Hartals){36}
2.8.4 解密(Crypt
Kicker){37}
2.8.5 完美洗牌术(Stack'em
Up){38}
2.8.6 Erd\"{o}s数(Erd\"{o}s
Numbers){41}
2.8.7 比赛记分板(Contest
Scoreboard){42}
2.8.8 Yahtzee
游戏(Yahtzee){43}
{2.9 习题 {45}
{2.10 注解 {45}
第3章 字符串
{47}
{3.1 字符编码 {47}
{3.2 字符串的表示
{49}
{3.3 程序设计实例:公司更名
{49}
{3.4 模式查找 {51}
{3.5 字符串操作
{52}
{3.6 程序的完成
{54}
{3.7 字符串库函数
{54}
{3.8 习题 {56}
3.8.1 WERTYU
键盘(WERTYU){56}
3.8.2 寻找单词(Where’s
Waldorf?){57}
3.8.3 公共排列(Common
Permutation){58}
3.8.4 解密II(Crypt Kicker
II){59}
3.8.5 自动评测脚本(Automated Judge
Script){60}
3.8.6 文件碎片(File
Fragmentation){62}
3.8.7 Doublet
序列(Doublets){63}
3.8.8 Fmt
程序(Fmt){63}
{3.9 提示 {65}
{3.10 注解 {65}
第4章 排序
{66}
{4.1 排序的应用
{66}
{4.2 排序算法 {67}
{4.3 程序设计举例:给绅士排名
{69}
{4.4 与排序相关的库函数
{71}
{4.5 给绅士排名
{72}
{4.6 习题 {75}
4.6.1 Vito 家族(Vito’s
Family){75}
4.6.2 煎饼堆(Stacks of
Flapjacks){75}
4.6.3
过桥(Bridge){76}
4.6.4 最长打盹时间(Longest
Nap){77}
4.6.5 鞋匠的烦恼(Shoemaker’s
Problem){79}
4.6.6 CDVII
高速公路(CDVII){80}
4.6.7
龟壳排序(ShellSort){81}
4.6.8 足球(Football (aka
Soccer)){82}
{4.7 提示 {84}
{4.8 注解 {85}
第5章 算术与代数
{86}
{5.1 机器算术 {86}
5.1.1
整数库函数{86}
{5.2 高精度整数
{87}
{5.3 高精度算术
{88}
{5.4 进制及其转换
{94}
{5.5 实数 {96}
5.5.1
如何处理实数{97}
5.5.2
分数{97}
5.5.3
十进制实数{98}
{5.6 代数 {98}
5.6.1
多项式运算{98}
5.6.2
多项式求根{99}
{5.7 对数 {100}
{5.8 实数函数库
{101}
{5.9 习题 {101}
5.9.1 小学生算术(Primary
Arithmetic){101}
5.9.2 反转相加(Reverse and
Add){102}
5.9.3 考古学家的烦恼(The
Archeologist’s Dilemma){103}
5.9.4
仅由1组成的数(Ones){104}
5.9.5 乘法游戏(A Multiplication
Game){104}
5.9.6 多项式的系数(Polynomial
Coefficients){105}
5.9.7 Stern-Brocot 代数系统(The
Stern-Brocot Number System){105}
5.9.8 两两之和(Pairsumonious
Numbers){106}
{5.10 提示 {107}
{5.11 注解 {108}
第6章 组合数学
{109}
{6.1 基本计数技巧
{109}
{6.2 递推关系
{110}
{6.3 二项式系数
{111}
{6.4 其他计数序列
{113}
{6.5 递归与数学归纳法
{115}
{6.6 习题 {116}
6.6.1 斐波那契计数(How Many
Fibs?){116}
6.6.2 土地分割(How Many Pieces of
Land?){116}
6.6.3
数数(Counting){117}
6.6.4
括号表达式(Expressions){118}
6.6.5 完全树标号(Complete Tree
Labeling){119}
6.6.6 牧师数学家(The Priest
Mathematician){119}
6.6.7 自描述序列(Self-describing
Sequence){120}
6.6.8
数轴行走(Steps){121}
{6.7 提示 {122}
{6.8 注解 {122}
第7章 数论
{123}
{7.1 素数 {123}
7.1.1
寻找素数{123}
7.1.2
素数的个数{124}
{7.2 整除性 {125}
7.2.1
最大公约数{125}
7.2.2
最小公倍数{127}
{7.3 模算术
{127}\vspace{0.15mm}
{7.4 同余
{129}\vspace{0.15mm}
7.4.1
同余运算{129}\vspace{0.15mm}
7.4.2
求解线性同余式{130}\vspace{0.15mm}
7.4.3
不定方程{131}\vspace{0.15mm}
{7.5 数论函数库
{131}\vspace{0.15mm}
{7.6 习题
{132}\vspace{0.15mm}
7.6.1 开灯与关灯(Light, More
Light){132}\vspace{0.15mm}
7.6.2 Carmichael 数(Carmichael
Numbers){132}\vspace{0.15mm}
7.6.3 欧几里德问题(Euclid
Problem){133}\vspace{0.15mm}
7.6.4
阶乘与整除(Factovisors){134}\vspace{0.15mm}
7.6.5 四素数之和(Summation of Four
Primes){134}\vspace{0.15mm}
7.6.6 Smith 数(Smith
Numbers){135}\vspace{0.15mm}
7.6.7
弹珠(Marbles){135}\vspace{0.15mm}
7.6.8
重新打包(Repackaging){136}\vspace{0.15mm}
{7.7 提示
{137}\vspace{0.15mm}
{7.8 注解
{137}\vspace{0.15mm}
第8章 回溯法
{138}\vspace{0.15mm}
{8.1 回溯法
{138}\vspace{0.15mm}
{8.2 构造所有子集
{140}\vspace{0.15mm}
{8.3 构造所有排列
{141}\vspace{0.15mm}
{8.4 程序设计举例:八皇后问题
{143}\vspace{0.15mm}
{8.5 搜索中的剪枝
{144}\vspace{0.15mm}
{8.6 习题
{147}\vspace{0.15mm}
8.6.1 棋盘上的象(Little
Bishops){147}\vspace{0.15mm}
8.6.2 15数码游戏(15-Puzzle
Problem){148}\vspace{0.15mm}
8.6.3
队伍(Queue){149}\vspace{0.15mm}
8.6.4 服务站(Servicing
Stations){150}\vspace{0.15mm}
8.6.5 拔河(Tug of
War){150}\vspace{0.15mm}
8.6.6 伊甸园(Garden of
Eden){151}\vspace{0.15mm}
8.6.7 色彩缤纷游戏(Color
Hash){153}\vspace{0.15mm}
8.6.8 拼接正方形(Bigger Square
Please...){154}\vspace{0.15mm}
{8.7 提示
{156}\vspace{0.15mm}
{8.8 注解
{156}\vspace{0.15mm}
第9章 图遍历
{157}
{9.1 图的不同属性
{157}
{9.2 图的数据结构
{158}
{9.3 图的遍历:宽度优先
{162}
9.3.1
宽度优先遍历{162}
9.3.2
遍历的应用{163}
9.3.3
寻找路径{164}
{9.4 图的遍历:深度优先
{165}
9.4.1
寻找环{166}
9.4.2
连通分量{167}
{9.5 拓扑排序
{168}
{9.6 习题 {170}
9.6.1
双着色(Bicoloring){170}
9.6.2 摆弄轮子(Playing With
Wheels){171}
9.6.3 导游(The Tourist
Guide){173}
9.6.4 斜线迷宫(Slash
Maze){174}
9.6.5 递变阶梯(Edit Step
Ladders){175}
9.6.6 立方体之塔(Tower of
Cubes){176}
9.6.7 从黄昏到拂晓(From Dusk till
Dawn){177}
9.6.8 汉诺塔卷土重来!(Hanoi Tower
Troubles Again!){179}
{9.7 提示 {179}
第10章 图算法
{181}
{10.1 图论 {181}
10.1.1
度的性质{181}
10.1.2
连通性{182}
10.1.3
图中的回路{182}
10.1.4
平面图{183}
{10.2 最小生成树
{183}
{10.3 最短路 {186}
10.3.1 Dijkstra
算法{186}
10.3.2
每对结点之间的最短路{188}
{10.4 网络流和二分图匹配
{191}
{10.5 习题 {195}
10.5.1
斑点(Freckles){195}
10.5.2 项链(The
Necklace){195}
10.5.3 消防站(Fire
Station){197}
10.5.4
铁路(Railroads){198}
10.5.5
战争(War){199}
10.5.6 导游(Tourist
Guide){201}
10.5.7 丰盛的晚餐(The Grand
Dinner){202}
10.5.8 命题者的难题(The Problem With
the Problem Setter){203}
{10.6 提示 {205}
第11章 动态规划
{206}
{11.1 慎用贪心法
{206}
{11.2 编辑距离
{207}
{11.3 重建路径
{211}
{11.4 编辑距离的变种
{212}
{11.5 程序设计举例:电梯优化
{214}
{11.6 习题 {218}
11.6.1 越大越聪明?(Is Bigger
Smarter?){218}
11.6.2 不同的子序列(Distinct
Subsequences){219}
11.6.3 重量和力量(Weights and
Measures){219}
11.6.4 单向TSP(Unidirectional
TSP){220}
11.6.5 切割小木棍(Cutting
Sticks){221}
11.6.6 渡船装载(Ferry
Loading){222}
11.6.7
筷子(Chopsticks){223}
11.6.8 搬家大冒险:第四部(Adventures
in Moving: Part IV){224}
{11.7 提示 {225}
{11.8 注解 {225}
第12章 网格
{226}
{12.1 矩形网格
{226}
12.1.1
遍历{227}
12.1.2
对偶图及其表示{228}
{12.2 三角形网格和六边形网格
{229}
12.2.1
三角形网格{229}
12.2.2
六边形网格{230}
{12.3 程序设计举例:西餐碟的重量
{232}
{12.4 给圆打包
{234}
{12.5 经度和纬度
{236}
{12.6 习题 {236}
12.6.1 棋盘上的蚂蚁(Ant on a
Chessboard){236}
12.6.2 独轮车(The
Monocycle){237}
12.6.3
六角星(Star){239}
12.6.4 蜜蜂Maja(Bee
Maja){240}
12.6.5
抢劫案(Robbery){241}
12.6.6 (2/3/4)-维立方体?((2/3/4)-D
Sqr/Rects/Cubes/Boxes?){242}
12.6.7 Dermuba 三角(Dermuba
Triangle){243}
12.6.8
航线(Airlines){244}
{12.7 提示 {246}
第13章 几何
{247}
{13.1 直线 {247}
{13.2 三角形和三角学
{250}
13.2.1
直角三角形和勾股定理{251}
13.2.2
三角函数{251}
13.2.3
解三角形{252}
{13.3 圆 {253}
{13.4 程序设计举例:超高速飞行
{255}
{13.5 三角函数库
{257}
{13.6 习题 {259}
13.6.1 狗拿地鼠(Dog and
Gopher){259}
13.6.2 绳子王国的危机!(Rope Crisis
in Ropeland!){260}
13.6.3 圆桌骑士(The Knights of the
Round Table){260}
13.6.4 巧克力片饼干(Chocolate Chip
Cookies){261}
13.6.5 生日蛋糕(Birthday
Cake){262}
13.6.6 最大/最小的盒子(The
Largest/Smallest Box ...){263}
13.6.7 要算积分吗?(Is This
Integration?){264}
13.6.8 它有多大?(How Big Is
It?){265}
{13.7 提示 {266}
第14章 计算几何
{277}
{14.1 线段及其相交
{277}
{14.2 多边形及旋转方向
{278}
{14.3 凸包 {270}
{14.4 三角剖分:算法与相关问题
{274}
14.4.1 Van Gogh
算法{274}
14.4.2
面积计算{276}
14.4.3
点定位{277}
{14.5 网格上的算法
{278}
14.5.1
范围查询{278}
14.5.2
网格多边形与Pick定理{279}
{14.6 几何函数库
{280}
{14.7 习题 {280}
14.7.1 新生集会(Herding
Frosh){280}
14.7.2 最近点对问题(The Closest Pair
Problem){281}
14.7.3 电锯惊魂(Chainsaw
Massacre){282}
14.7.4 冷热游戏(Hotter
Colder){283}
14.7.5 没用的瓷砖打包公司(Useless
Tile Packers){284}
14.7.6 雷达追踪(Radar
Tracking){285}
14.7.7 岛上的树(Trees on My
Island){286}
14.7.8 美味的牛奶(Nice
Milk){287}
{14.8 提示 {288}
附录A
{290}
{A.1 ACM 国际大学生程序设计竞赛
{290}
A.1.1
准备{290}
A.1.2
战略战术{292}
{A.2 国际信息学奥林匹克
{293}
A.2.1
如何参加{293}
A.2.2
比赛形式{294}
A.2.3
准备{295}
{A.3 Topcoder.com
{295}
{A.4 念研究生吧!
{296}
{A.5 题目致谢
{297}
参考文献
{300}