OJ3-3_气象台_KD树

思路

KD树的结构

每群点可看成一个矩形，矩形为覆盖这群点的最小矩形

单个点也可以看作是一个退化了的矩形

对矩形进行不断分割，横着切或竖着切，以此来构成一棵树

图中绿色的矩形为树根，红色的矩形为树根的两个子节点……叶子节点为单个点构成的矩形（图中没有画出来）

程序主体思路

树节点存储的信息：本树下所有节点组成的一个矩形的四条边的位置，本结点的温度总和，节点数。

1.建树

将所有点的信息放入一个数组中，每次按x或按y找到其最中间的点。

把数组分成两半，将两边的点分别放到下一层递归中，直到只剩一个点。（相当于把一个矩形拆分成两个矩形，直到矩形中只剩一个点）

若是叶子节点则写入本结点的信息，若是内部节点则根据子节点的信息填写父节点的信息。

2.查找

三种情况：

1）查找矩形覆盖本矩形：直接将本矩形的温度总和和节点数参与计算

2）不相交：直接return

3）其他情况（有交集但不覆盖）：调用子节点两个矩形进一步判断

伪代码

global temperature,number

//按照x坐标区分进行建树
buildtree_by_x(node, array):
    if array.lenth==1:
        store information in node
        return
    find mid point of the array by x(you can use quick select)
    use mid to divide the array into two part, array_front and array_back
    buildtree_by_y(node.leftchild, array_front)
    buildtree_by_y(node.rightchild, array_back)
    calculate the information and store it in node

//按照y坐标区分进行建树
buildtree_by_y(node, array):
    if array.lenth==1:
        store information in node
        return
    find mid point of the array by y(you can use quick select)
    use mid to divide the array into two part, array_front and array_back
    buildtree_by_x(node.leftchild, array_front)
    buildtree_by_x(node.rightchild, array_back)
    calculate the information and store it in node

//搜索，将结果保存在两个全局变量里
search(node,rect):
    if root ∩ rect == emptyset:
        return
    if root in rect:
        temperature+=node.temp
        number+=node.num
        return
    search(node.leftchild)
    search(node.rightchild)

main():
    buildtree_by_x(root, array)
    for i from 1 to n:
        temperature=0
        number=0
        rect=input()
        search(root,rect)
        if number!=0:
            aver=temperature/number 

更多优化

如果有同学对这个题感兴趣，还想进一步优化的话可以学习一下range tree结构和fractional cascading算法，可以把运行时间提升到1133ms

本站总访问量次

评论