2932 Coneology

Posted on 2010-03-10 13:05 王之昊 阅读(582) 评论(0)  编辑 收藏 引用 所属分类: pku
    考虑扫描线,选择一个圆的最左点和最右点作为事件点.然后用一条竖直线从左到右扫一遍.
    维护一个数据结构,里面保存着和扫描线相交的powerful 圆.
    如果一个事件是某圆的最右点,并且该圆在数据结构中,就意味着要把这个圆删掉.
    如果一个事件是某圆的最左点,当它不被其他圆包含时,就意味着可能要把它加入到我们的数据结构中,
怎么检查它有没有被其他圆包含呢?我们的数据结构里的圆都是一些 powerful 圆,他们互不相交,也就是
说他们在当前的扫描线上占的区间也互不相交, 如果我们只是记录圆心在扫描线的投影, 把高的投影称为前,
把低的投影低称为后,那么可能与当前圆发生关系的只是它的前一个圆,后一个圆.



然后来决定数据结构,要满足插入一个圆,删除一个圆,询问前一个圆,询问后一个圆.map就可以胜任了.



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊