信息学奥林匹克竞赛:国际国内分类试题精解(2003-2004)(下册)(中国计算机学会信息学奥林匹克系列丛书)
点此进入淘宝搜索页搜索分类: 图书,考试,奥赛/竞赛,综合,
品牌: 吴文虎
基本信息·出版社：清华大学出版社
·页码：148 页
·出版日期：2008年
·ISBN：7302169241/9787302169246
·条形码：9787302169246
·包装版本：1版
·装帧：平装
·开本：16
·正文语种：中文
·读者对象：中小学生
·丛书名：中国计算机学会信息学奥林匹克系列丛书
产品信息有问题吗？请帮我们更新产品信息。
内容简介《中国计算机学会信息学奥林匹克系列丛书》由中国计算机学会信息学奥林匹克学委员会主编，由全国著名专家学者精心编著而成。《信息学奥林匹克竞赛-国际国内分类试题精解(2003-2004)下册》收录了2003－2004年国际国内信息学奥林匹克的大部分试题。全书对试题进行了类型归纳，并分上、下两册出版。上册包括基础类试题、数据结构类试题、搜索类试题和动态程序设计类试题。下册包括计算几何类试题和构造类试题。全书对每种类型试题做了简要的介绍，所有的试题都给出了具体的算法分析和相应的源代码。
编辑推荐《信息学奥林匹克竞赛-国际国内分类试题精解(2003-2004)下册》既适合教师辅导学生使用，也适合参加信息学奥林匹克竞赛的学生自学，同时也是大专院校的计算机爱好者学习编程的优秀参考书。
目录
第6章计算几何类试题
6.1女神
6.2多边形
6.3降雨量
6.4最优切割
6.5卫星探测
6.6卫星探测
6.7可视边界
第7章构造类试题
7.1逆向输出
7.2公式编辑器
7.3零件装配
7.4猜牛游戏
7.5沙丘
7.6信使
7.7石器时代
7.8数字搜索
……[看更多目录]
序言信息技术对人类社会的发展产生着深远的影响，已成为21世纪的一个标志。作为人类集体智慧的结晶，信息技术已成为一种时代文化。“计算机的普及要从娃娃抓起”成为“科教兴国”的一项重要内容。
一个国家、一个民族要立足于世界先进民族之林，关键在于拥有高素质的人才。综合国力的竞争，说到底是人才的竞争，培养和造就一大批优秀信息技术人才是当务之急。信息时代，信息技术已成为现代科学与技术的基础核心，成为人类的“通用智力工具”，在青少年中普及信息技术教育具有重要和深远的意义。
中国计算机学会从1984年起，就组织青少年参加信息学奥林匹克竞赛。二十余年，学会通过组织竞赛推动信息技术普及，促进青少年掌握信息技术知识，并提高他们的逻辑思维和解决问题的能力。为了培养和造就更多高素质的信息技术人才，中国计算机学会特别推出一套信息学奥林匹克系列指导丛书。
文摘只要我们能够设计出状态转移方程f和f'，便可以通过动态程序设计方法解出此题。有兴趣的读者不妨试一试。
另外，如果变换试题条件的话，则可以拓展出许多开放性问题和探究性问题。例如：
·如果要找一个边平行于坐标轴，且内含的点数（包括两个给定的对角点）在至多有
T个点的前提下尽可能大的矩形，怎么办？
·如果要找的矩形，内含点的要求不变，但边不平行于坐标轴（边与坐标轴的角度限
定在某范围内），怎么办？
·如果要找的是内含点数（包括圆弧上的点）在至少有T个点的前提下尽可能小的
一个圆，怎么办？等等。
如果通过对这些相近、相关问题（即形式不同、本质类似的一类问题）的归纳，能揭示出内在的联系，概括出解决类似问题的一般规律，并得到高度抽象、概括的模型的话，其意义自然超过解题本身。
6.2 多边形
【问题描述】多边形是由其边线上及边线范围内的所有点构成的。凸多边形有如下特征，即连接该多边形任意两点的线段是在多边形的内部。本题中的多边形都是指至少有两个顶点的凸多边形，所有的顶点都是整数坐标，并且各不相同，且没有三点共线以下“多边形”指的都是这样的凸多边形。
假定有两个多边形A和B（线段也算是特殊的多边形，但一个点不是多边形）。对于多边形A和B，它们的Minkowski和由（x1+x2，y1+y2）图形中的所有的点构成，其中（xl，y1）是A中的一个点，（x2，y2）是B中的一个点。因此，Minkowski和也是一个多边形。图6-9给出了两个三角形及它们的Minkowski和。
插图：
