1.1 引言 当今世界，“程序员”这么一个职业名称可分为很多类型，比如SI程序员、数据库程序员、网页设计程序员、游戏设计程序员，等等。这些程序员在不同的开发环境下，利用不同的程序语言和工具编写程序，解决各自面临的问题。那么，要成为跨领域的优秀程序员需要具备什么样的条件呢？ 程序设计就是解决问题... 查看全部[ 1.1 引言 ]
参加程序设计竞赛是培养解决问题能力的最佳途径。在目前各式各样的程序设计竞赛当中，本书选取设计要求较少、有运算时间限制、比拼快速设计能力的竞赛。此处的设计要求不同于实际开发中的要求，而是以“读入某个值，然后计算出某个值”的形式给出。 下面针对未接触过程序设计竞赛的读者举个简单的示例。 题目：摇滚... 查看全部[ 1.2 程序设计竞赛 ]
本书结构 本书共由7个部分组成。为学好后半部分的内容，第一部分和第二部分主要介绍了一些背景知识，其中包括程序设计竞赛中解决问题的方法、编写代码和调试中的注意事项、算法的正确性证明以及效率分析等。不要以为此部分是基础性的内容而可以忽视，如果不能很好地理解这些基础知识，那么之后更深的内容就只能学到皮毛... 查看全部[ 1.3 阅读本书的方法 ]
国内外目前有很多程序设计竞赛。过去的竞赛参赛者大多为学生，但随着软件公司开始注重应聘者解决算法问题的能力 ，现在也出现了面向公众的程序设计竞赛。下面这些竞赛值得各位一试。 全国青少年信息学奥林匹克竞赛 关于NOI（National Olympiad in Informatics）：http://... 查看全部[ 1.4 值得参加的程序设计竞赛 ]
下面为准备参加程序设计竞赛的本书读者们提供一些建议。 尽可能多解题 参加程序设计竞赛需要学习的内容非常多。以本书为例，全书有32章之多，但其内容还不能完全涵盖竞赛的所有主题。海量的学习内容很容易让参赛者陷入“尽可能多读教科书和其他资料来补充基础知识”的误区。其实，多了解一个算法，还不如提高利用... 查看全部[ 1.5 对赛前准备工作的一些建议 ]
功能更强、更有用的参考资料是互联网和搜索引擎。与“教科书万能”的时代不同，现在有了维基百科（http://wikipedia.org）等网站，没有课本也能好好学习。不管是本书内容还是其他主题，都能轻而易举地搜索到相关资料。 “知道自己不知道”的时候，搜索和互联网还是非常有用的。但迷茫于不知道该学什... 查看全部[ 1.6 续读 ]
2.1 引言 第1章中提到过，程序设计竞赛是培养解决问题能力的理想环境。但并不能通过死记硬背算法去拼命解题而培养出来。解决问题的能力不同于程序设计和算法，它没有实体性的定义可循，而是一种抽象概念。因此，只靠单纯的反复练习很难培养。大多数读者小学开始就已经学解算术题，但那只是针对给出题目的解题方法。... 查看全部[ 2.1 引言 ]
首先介绍现今最流行的一个解决问题的算法，它因著名量子物理学家理查德•费曼（Richard Feynman）最早使用而得名。这个算法不仅功能强大，而且包含了解决问题所需的全部因素。费曼利用此算法解决了量子力学方面的诸多难题。 下面是费曼算法的详解。 1. 把问题写到黑板上； 2. 冥思苦想；... 查看全部[ 2.2 解决问题的过程 ]
遇到简单的问题时，直接利用已知技术便可轻松解决问题。若是遇到难题，需试用各种手段去寻找答案。本节先介绍几个最常用的策略，之后再介绍应用这些策略的示例。本书习题中大量使用这些策略，希望各位阅读解题过程时，留意着手解题的方法。 直观而系统的着手方式 解决问题的策略中，首先强调的是对问题和答案结构的... 查看全部[ 2.3 解决问题的策略 ]
作为解决问题领域的经典书籍，《如何求解问题：现代启发式方法》（How to Solve It: Modern Heuristics）列出了许多解决问题的策略，也介绍了许多初次遇到的问题的解法。... 查看全部[ 2.4 续读 ]
15.1 引言 与点、线、多边形、圆形等各种几何图形相关的算法称为计算几何（computational geometry）算法。计算几何已成为3D图形、CAD、机器人等多种领域的基础，在计算机学科中占据了重要地位。程序设计竞赛中也常常出现有关计算几何的问题。 计算几何包含了很多内容，涉及面非常广... 查看全部[ 15.1 引言 ]
首先定义编写计算几何代码时必须用到的概念，并观察其实现方法。 向量的实现 二维平面上的两个不同点的相对位置该如何表示呢？对于这个问题，应当先求出两点之间的距离，然后求出从一个点到另外一个点的方向。求出方向和距离后，就能准确表示出两点之间的相对位置。这种既有大小又有方向的距离就是向量（vecto... 查看全部[ 15.2 计算几何的工具 ]
直线与直线相交 确认两条直线是否相交并求出交点的问题在几何题中很常见。求两条直线交点的数学问题并不难，不过，要编写出没有异常的代码就比较困难了。解出x坐标后代入方程求出y坐标的程序，会无法应对水平线和垂直线等特殊的情况。因此，无论用何种方法编写程序，都要考虑到特殊情况。 表示相交直线的最好方法是... 查看全部[ 15.3 相交、距离、面积 ]
东赫在玩一种新出的弹球游戏，这种弹球游戏会在一个很大的游戏台中放置几个障碍物，然后让玩家抛进小球，撞击障碍物最多的人获胜。小球和障碍物都是正圆，小球撞击障碍物后的入射角和反射角相同。障碍物已固定到游戏台上，不可移动。下图表示东赫依序抛进的小球撞击各障碍物后，弹出游戏台的路线。 给出障碍物的大小... 查看全部[ 15.4 练习题：弹球模拟（题目 ID：PINBALL，难度：高） ]
若是用方程式解决此问题，将会变得非常复杂，利用向量就简单得多了。 简化问题 首先介绍简化问题的方法。题目中，小球是半径为1的圆形。将小球简化成点，并把所有障碍物的半径加1，这样就能把相同的球作为点求解。虽然这种简化并不能让题目更简单，但是小球的运动轨迹可以变成一条直线，对解题也比较有利。 状态... 查看全部[ 15.5 解题：弹球模拟 ]
以计算几何方式表现现实世界时，多边形（polygon）是必不可少的因素。因此，有关多边形的问题也经常出现在程序设计竞赛中。 多边形的种类 首先简单介绍本节将要用到的名词。 凸多边形（convex polygon）指的是每个内角都在180度以内的多边形。例如，正方形就是凸多边形。凸多边形具有... 查看全部[ 15.6 多边形 ]
人们历经磨难，终于找到了著名海盗Guybrush Threepwood藏匿宝箱的金银岛。虽然已经知道Guybrush肯定把宝箱藏在了此岛，但具体的藏匿位置仍然不得而知。快要翻遍整个小岛时，发现了地图上未能标出的写有宝箱埋藏位置的纸条。纸条对宝箱的位置进行了详细说明，不过，因为写得过于繁琐，而且有多处... 查看全部[ 15.7 练习题：金银岛（题目 ID：TREASURE，难度：高） ]
多边形的交集 解决此问题的最直观的方法是，先求出两个简单多边形的交集，然后求交集面积。两个多边形都是凸多边形时，最容易求出多边形的交集，因为两个凸多边形的交集也是凸多边形。不过此题中，小岛的轮廓是任意简单多边形，所以此性质并不成立。所幸第二个多边形是矩形，所以是凸多边形，问题也就变得简单了。 ... 查看全部[ 15.8 解题：金银岛 ]
一年一度的algospot程序设计竞赛日益临近，今年的竞赛非常火爆，报名人数超过了1万人。不过，参加评判的志愿者只有5人，所以不能让所有报名者全部参赛。因此，组织方决定，只让“真正的编程呆子（nerd）”参加竞赛。 根据宗万的新理论，某人的呆子指数可以用如下两种数值的线性结合定义。 F=A×鞋... 查看全部[ 15.9 练习题：是呆子？不是呆子？（题目ID：NERDS，难度：中） ]
变换成几何问题 此题看似完全不是几何题，其实，巧妙变换即可。实行变换的第一个线索是，每人有两项调查资料，因此，把每人的鞋子尺码和每分钟的打字速度分别视为x、y坐标，就能把输入的数据表示成N个点。图15-13(a)是第一个示例的图形，图中的○表示呆子，×表示不是呆子的人。每个人的信息已表示成图表形式... 查看全部[ 15.10 解题：是呆子？不是呆子？ ]
很多计算几何问题都可以利用本章介绍的相关代码组合解决，不过，只解决固定模式的问题并不是几何问题的全部内容。很多情况下需要组合这些代码，以编写出更复杂的算法。此时，几何算法的设计范式将有助于编写出更高效的算法。本节将介绍两种比较著名的范式，并通过示例讲解如何利用这些范式提高解题效率。 平面扫描 ... 查看全部[ 15.11 计算几何算法设计范式 ]
计算几何在程序设计竞赛中比较臭名昭著的原因是，其本质上存在较多异常情况。 退化图形 设计几何算法时的常见失误是，只考虑图像的“一般位置”（general position）。一般位置指的是图形相对位置的一般情况。与其对应的异常情况称为退化（degenerate）图形，如下所示。 同一直线上... 查看全部[ 15.12 常见失误与注意事项 ]
拥有大量计算几何习题及解法的网站（http://softsurfer.com/）提供了本章算法的详细说明和C++代码。 针对平面扫描问题的TopCoder教程（http://links.algospot.com/linesweep）介绍了能够用平面扫描方法解决的题目及简单解法。 介绍... 查看全部[ 15.13 续读 ]