#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> #define alpha (0.75) using namespace std; const int N = 6e5 + 5; const int INF = 0x3f3f3f3f; bool dimension; bool reg_dimension; int n, m, ans; struct Point { int x, y; Point(int X = 0, int Y = 0) :x(X), y(Y) {} }; Point a[N]; struct Node *null; struct Node { int cover; Point p, r1, r2; Node *son[2]; inline void maintain() { r1.x = min(r1.x, min(son[0]->r1.x, son[1]->r1.x)); r1.y = min(r1.y, min(son[0]->r1.y, son[1]->r1.y)); r2.x = max(r2.x, max(son[0]->r2.x, son[1]->r2.x)); r2.y = max(r2.y, max(son[0]->r2.y, son[1]->r2.y)); cover = son[0]->cover + son[1]->cover + 1; } inline bool is_bad() { return max(son[0]->cover, son[1]->cover) > cover*alpha + 5; } inline int dis(Point p) { if (this == null)return INF; int res = 0; //曼哈顿距离 if (p.x<r1.x || p.x>r2.x)res += p.x < r1.x ? r1.x - p.x : p.x - r2.x; if (p.y<r1.y || p.y>r2.y)res += p.y < r1.y ? r1.y - p.y : p.y - r2.y; return res; } }; Node mempool[N]; Node *tail; Node *root; inline bool cmp(Point p1, Point p2) { if (dimension == 0)return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x); } inline int Manhattan_dis(Point a, Point b)//曼哈顿距离 { return abs(a.x - b.x) + abs(a.y - b.y); } inline double Oshi_dis(Point a,Point b) { return sqrt(1.0*(a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); } inline void init() { tail = mempool; null = tail++; null->son[0] = null->son[1] = null; null->r1 = Point(INF, INF); null->r2 = Point(-INF, -INF); null->cover = 0; root = null; } inline Node* new_node(Point key) { Node *o; o = tail++; o->son[0] = o->son[1] = null; o->cover= 1; o->p = o->r1 = o->r2 = key; return o; } inline void travel(Node* p, vector<Node*>&x) { if (p == null)return; travel(p->son[0], x); x.push_back(p); travel(p->son[1], x); } inline Node* divide(vector<Node*>&x, int l, int r, bool d) { if (l >= r)return null; int mid = (l + r) >> 1; dimension = d; Node *o = x[mid]; o->son[0] = divide(x, l, mid, d ^ 1); o->son[1] = divide(x, mid + 1, r, d ^ 1); o->maintain(); return o; } inline void rebuild(Node *&o, bool d) { static vector<Node*>v; v.clear(); travel(o, v); o = divide(v, 0, v.size(), d); } inline Node* build(int l, int r, bool d) { if (l >= r)return null; int mid = (l + r) >> 1; dimension = d; nth_element(a + l, a + mid, a + r, cmp); Node *o = new_node(a[mid]); o->son[0] = build(l, mid, d ^ 1); o->son[1] = build(mid + 1, r, d ^ 1); o->maintain(); return o; } inline Node** __insert(Node *&o, Point key) { if (o == null) { o = new_node(key); reg_dimension = dimension; return &null; } else { o->cover++; bool dir = cmp(key, o->p) ^ 1; dimension ^= 1; Node** res = __insert(o->son[dir], key); if (o->is_bad()) { res = &o; reg_dimension = dimension;//记录递归过程中最后一个较为不平衡的结点 } o->maintain(); return res; } } inline void insert(Point key) { reg_dimension = dimension = 0; Node** res = __insert(root, key); if (*res != null)rebuild(*res, reg_dimension); } inline void query(Node *o, Point key) { if (o == null)return; ans = min(ans, Manhattan_dis(key, o->p)); int dir = o->son[0]->dis(key) > o->son[1]->dis(key); query(o->son[dir], key); if (o->son[dir ^ 1]->dis(key) < ans) query(o->son[dir ^ 1], key); } inline int read() { char ch = getchar(); int f = 1, x = 0; while (ch > '9' || ch < '0') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { init(); n = read(); m = read(); for (int i = 0; i < n; i++) a[i].x = read(), a[i].y = read(); root = build(0, n, 0); while (m--) { int op = read(), x = read(), y = read(); if (op == 1)insert(Point(x, y)); else { ans = INF; query(root, Point(x, y)); printf("%d ", ans); } } return 0; }