《acm培训资料》word版

《《acm培训资料》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、计算几何基础　　　　　　　　　　　　　　　　　　目　录第一篇入门篇1第1章新手入门21ACM国际大学生程序设计竞赛简介22ACM竞赛需要的知识33团队配合54练习、练习、再练习55对新手的一些建议6第2章C++语言介绍81C++简介82变量83C++数据类型94C++操作符105数组126字符数组137字串操作函数148过程控制169C++中的函数1910函数规则21第3章STL简介221泛型程序设计222STL的组成26第二篇算法篇45第1章基本算法461算法初步462分治算法513搜索算法544贪婪算法60第2章进阶算法701数论基础702图论算法763计算几何基础93第三

2、篇实践篇106第1章《多边形》107第2章《灌溉问题》110第3章《Lgame》113第4章《number》解题报告117第5章《Jobs》解题报告119第6章《包裹运送》122第7章《桶的摆放》124105计算几何基础　　第一篇入门篇练就坚实的基础，总有一天……我们可以草木皆兵！105计算几何基础　　第1章新手入门1ACM国际大学生程序设计竞赛简介1.1背景与历史1970年在美国TexasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别，即区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区

3、域赛点。1995至1996年，来自世界各地的一千多支高校的代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。1.2 竞赛组织竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至12月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个

4、学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。1.3竞赛形式与评分办法竞赛进行5个小时，一般有6~10道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。程序运行不正确是指出

5、现以下4种情况之一：(1)运行出错(run-time error)；(2)运行超时(time-limit exceeded)；(3)运行结果错误(wrong answer)；(4)运行结果输出格式错误(presentation error)。竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时（每次提交通不过，罚时20105计算几何基础　　分钟）。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料（包括试题）将用美国英语写

6、出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。1.1竞赛奖励情况总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。2ACM竞赛需要的知识2.1编程语言是最重要的基本功无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，编程语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与Java。首先

7、说说Java，众所周知，作为面向对象的王牌语言，Java在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，Java则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是Java程序的运行速度要比C++慢10倍以上，而竞赛中对于Java程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降