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