Description

为了写论文,Alex经常要整理大量的数据。 这一次,Alex面临一个严峻的考验:他需要实现一个数据结构来维护一个点集。
现在,二维平面上有N个点。Alex 需要实现以下三种操作:
1. 在点集里添加一个点;
2. 给出一个点,查询它到点集里所有点的曼哈顿距离的最小值;
3. 给出一个点,查询它到点集里所有点的曼哈顿距离的最大值。
两个点的曼哈顿距离定义为它们的横坐标差的绝对值与纵坐标差的绝对值的和。这么困难的问题,Alex当然不会做,只好再次请你帮忙了。

Input

第一行包含一个整数N,表示点集最初的点数。
接下来N行,每行两个整数,依次表示每个点的横坐标和纵坐标。
第N+2行包含一个整数Q,表示询问的数目。
接下来Q行,每行三个整数,依次表示询问的类型,点的横坐标和纵坐标。0类型表示添加一个点,1类型表示查询到该点的曼哈顿距离的最小值,2类型表示查询最大值。
1 ≤ N, Q ≤ 100,000,点的坐标是不超过10^9的非负整数

Output

输出若干行,依次表示每个查询操作的答案。

Sample Input

3
7 5
6 2
3 1
5
1 6 1
1 5 5
2 7 1
0 3 2
1 1 0

Sample Output

1
2
4
3
复习熟练一下kd-tree的写法qwq
求曼哈顿距离最小值:
估价函数为该点到边框矩形的最小值 然后优先去做估价小的子树 程序中的calc1函数
求曼哈顿距离最大值:
估价函数为该点到边框矩形的最大值 然后优先去做估价大的子树 程序中的calc2函数
为了保证是时间复杂度 每10000个暴力重构 注意在建树以及insert1的时候要将左右子树指针清空

 

分类: kd-tree

elijahqi

本人蒟蒻qwq 欢迎加qq虐qwq 2922945330

发表评论

电子邮件地址不会被公开。 必填项已用*标注