找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1782|回复: 3
收起左侧

[刷题心得] 转一个讲扫描线算法的好帖子

[复制链接]

3

主题

0

精华

31

积分

新米人

Rank: 1

积分
31
发表于 9-19-2017 10:26 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
平面扫描思想在ACM竞赛中的应用
Jan 1, 2013
【i】说明:以下为本科挫比的比赛论文,写文章的语气都是一副叫兽的调调!
         摘要: 平面扫描思想在计算几何,计算机图形学,网格计算等计算机理论领域有广泛的应用。有非常多的经典算法借助平面扫描的思想极大的降低了算法时间复杂度。例如线段相交问题、平面上多矩形轮廓算法、平面多矩形求交、空间冲突检测算法、Voronoi图构造算法、平面最近点对等等。
        本文介绍了在ACM程序设计竞赛中经常用到的几个平面扫描算法。根据这些算法的作用,大致分为以下几类:
  • 数据统计;
  • 几何实体位置关系的检测;
  • 最近点对。 本文依次选取了三类算法中具有代表性的经典算法加以介绍,并有针对性的剖析了大量经典ACM算法竞赛试题,以期对ACM程序设计竞赛参赛者起到抛砖引玉的作用。
关键字
【i】平面扫描 ; 【i】ACM大学生程序设计竞赛 ; 【i】算法 ; 【i】数据统计 ; 【i】几何实体位置关系; 【i】最近点对
第一章:引言
        ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate Programming Contest(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近30多年的发展,ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。
        竞赛的历史可以上溯到1970年,当时在美国德克萨斯A&M大学举办了首届比赛。当时的主办方是the Alpha Chapter of the UPE Computer Science Honor Society。作为一种全新的发现和培养计算机科学顶尖学生的方式,竞赛很快得到美国和加拿大各大学的积极响应。1977年,在ACM计算机科学会议期间举办了首次总决赛,并演变成为目前的一年一届的多国参与的国际性比赛。迄今已经举办了35届。
        平面扫描思想是一种在计算几何、计算机图形学等领域经常用到的算法优化思想。由于ACM程序设计竞赛是一类对算法时间复杂度和空间复杂度要求非常高的高水平竞赛。竞赛中出现的许多的计算几何题目和高级数据结构题目都可以通过运用平面扫描的思想优化时空复杂度,使得程序能在题目给定的时间限制和空间限制下快速求出问题的解。
        平面扫描算法一般由扫描线、事件点和当前扫描线事件点集合三个部分组成。扫描线一般是一根平行于坐标轴的水平线(或垂直线)。它按照从上到下(或从左到右)的顺序,依次检测事件点,通过删除或新增事件点来维护当前扫描线事件点集合。当前扫描线事件点集合通常都是用线段树、树状数组、红黑树等平衡二叉树来维护的,特殊情况下也需要用Hash表、块状表、跳跃链表等高级数据结构来达到维护目的。通过查询当前扫描线事件点集合的相关信息,我们就可以获得问题的答案。
        正文将ACM竞赛中的扫描线算法分成三类,并依次介绍相关类型的算法。希望对参赛者的算法学习有所帮助。
第二章:算法介绍及试题剖析第一节:数据统计
经典问题A 平面坐标系上有N个矩形,这些矩形的四条边都平行于X轴或Y轴。每个矩形可以被其他矩形部分或者完全遮盖,所有矩形合并成区域的边界周长称为轮廓周长。例如图1中所有矩形的轮廓如图2所示:

请设计一个算法,计算所有矩形的轮廓周长。
输入 平面上N个矩形,第i个矩形用左下顶点坐标(Xi, Yi)和右上顶点坐标(UXi, UYi)表示。
输出 所有矩形轮廓周长。
算法分析 先离散化。用每个矩形的四边所在直线将二维平面切割。这样,就只要考虑AB这样的单元线段了。把组成轮廓的单元线段长度相加就是矩形轮廓周长和。假设L1, L2 …, L8 各竖直线经过映射后对应于mapx1,mapx2 …, mapx8。为方便描述,令mapx0=mapx1。

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 9-21-2017 11:52 AM | 显示全部楼层
感谢squarelawrence分享~~~
回复 支持 反对

使用道具 举报

1117

主题

164

精华

3414

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3414
发表于 9-22-2017 10:17 AM 来自美国米群网手机版 | 显示全部楼层
感谢squarelawrence分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表