[BZOJ1941][Sdoi2010]Hide and Seek
试题描述
小猪iPig在PKU刚上完了无聊的猪性代数课，天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞，为了消除寂寞感，他决定和他的好朋友giPi（鸡皮）玩一个更加寂寞的游戏---捉迷藏。 但是，他们觉得，玩普通的捉迷藏没什么意思，还是不够寂寞，于是，他们决定玩寂寞无比的螃蟹版捉迷藏，顾名思义，就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后，他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了，所以giPi只会躲在PKU内n个隐秘地点，显然iPig也只会在那n个地点内找giPi。游戏一开始，他们选定一个地点，iPig保持不动，然后giPi用30秒的时间逃离现场（显然，giPi不会呆在原地）。然后iPig会随机地去找giPi，直到找到为止。由于iPig很懒，所以他到总是走最短的路径，而且，他选择起始点不是随便选的，他想找一个地点，使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑，所以不能编程解决这个如此简单的问题，所以他马上打了个电话，要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标，请你编程求出iPig的问题。
输入
第一行输入一个整数N 第2~N+1行，每行两个整数X，Y，表示第i个地点的坐标
输出
第一行输入一个整数N 第2~N+1行，每行两个整数X，Y，表示第i个地点的坐标
输入示例
4 0 0 1 0 0 1 1 1
输出示例
1
数据规模及约定
对于30%的数据,N<=1000 对于100%的数据，N<=500000,0<=X,Y<=10^8 保证数据没有重点保证N>=2
题解
kd树模板题，对于每一个点算一下除它之外的最远和最近距离。
既然要“除它之外”，那么设计一个删除操作将删除的点打一个标记，询问完后再删除标记。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
#define LL long long
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
LL read() {
LL x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 500010
#define oo 1047483647
int n, ToT, lc[maxn], rc[maxn], nx[maxn], ny[maxn], root;
bool Cur;
struct Node {
int x[2], mx[2], mn[2];
bool del;
bool operator < (const Node& t) const { return x[Cur] == t.x[Cur] ? x[Cur^1] < t.x[Cur^1] : x[Cur] < t.x[Cur]; }
bool operator == (const Node& t) const { return x[0] == t.x[0] && x[1] == t.x[1]; }
int operator * (const Node& t) const { return abs(x[0] - t.x[0]) + abs(x[1] - t.x[1]); }
} ns[maxn];
void maintain(int o) {
int l = lc[o], r = rc[o];
for(int i = 0; i < 2; i++) {
ns[o].mx[i] = max(max(ns[l].mx[i], ns[r].mx[i]), ns[o].del ? -oo : ns[o].x[i]);
ns[o].mn[i] = min(min(ns[l].mn[i], ns[r].mn[i]), ns[o].del ? oo : ns[o].x[i]);
}
return ;
}
void build(int& o, int L, int R, bool cur) {
if(L > R){ o = 0; return ; }
int M = L + R >> 1; o = M;
Cur = cur; nth_element(ns + L, ns + M, ns + R + 1);
build(lc[o], L, M - 1, cur ^ 1); build(rc[o], M + 1, R, cur ^ 1);
maintain(o);
return ;
}
Node x;
void remove(int o, bool cur) {
Cur = cur;
if(!o) return ;
if(x == ns[o]){ ns[o].del = 1; return maintain(o); }
remove(x < ns[o] ? lc[o] : rc[o], cur ^ 1);
return maintain(o);
}
void insert(int o, bool cur) {
Cur = cur;
if(!o) return ;
// if(x == ns[o]) printf("%d: %d %d
", o, ns[o].x[0], ns[o].x[1]);
if(x == ns[o]){ ns[o].del = 0; return maintain(o); }
insert(x < ns[o] ? lc[o] : rc[o], cur ^ 1);
return maintain(o);
}
int calcmx(int o) { return max(abs(ns[o].mx[0] - x.x[0]), abs(ns[o].mn[0] - x.x[0])) + max(abs(ns[o].mx[1] - x.x[1]), abs(ns[o].mn[1] - x.x[1])); }
int querymx(int o) {
if(!o) return -oo;
int ans = -oo;
if(!ns[o].del) ans = max(ans, ns[o] * x);
int dl = calcmx(lc[o]), dr = calcmx(rc[o]);
if(dl > dr) {
if(dl > ans) ans = max(ans, querymx(lc[o]));
if(dr > ans) ans = max(ans, querymx(rc[o]));
}
else {
if(dr > ans) ans = max(ans, querymx(rc[o]));
if(dl > ans) ans = max(ans, querymx(lc[o]));
}
return ans;
}
int calcmn(int o) {
int ans = 0;
for(int i = 0; i < 2; i++) {
if(x.x[i] > ns[o].mx[i]) ans += x.x[i] - ns[o].mx[i];
if(x.x[i] < ns[o].mn[i]) ans += ns[o].mn[i] - x.x[i];
}
return ans;
}
int querymn(int o) {
if(!o) return oo;
int ans = oo;
if(!ns[o].del) ans = min(ans, ns[o] * x);
int dl = calcmn(lc[o]), dr = calcmn(rc[o]);
if(dl < dr) {
if(dl < ans) ans = min(ans, querymn(lc[o]));
if(dr < ans) ans = min(ans, querymn(rc[o]));
}
else {
if(dr < ans) ans = min(ans, querymn(rc[o]));
if(dl < ans) ans = min(ans, querymn(lc[o]));
}
return ans;
}
int main() {
ns[0].mx[0] = ns[0].mx[1] = -oo;
ns[0].mn[0] = ns[0].mn[1] = oo;
n = read();
for(int i = 1; i <= n; i++) {
nx[i] = ns[++ToT].x[0] = read(); ny[i] = ns[ToT].x[1] = read();
ns[ToT].del = 0;
}
build(root, 1, n, 0);
int ans = oo;
for(int i = 1; i <= n; i++) {
x.x[0] = nx[i]; x.x[1] = ny[i];
remove(root, 0);
ans = min(ans, querymx(root) - querymn(root));
// printf("%d %d
", querymx(root), querymn(root));
insert(root, 0);
}
printf("%d
", ans);
return 0;
}
/*
6
0 0
1 1
0 9
9 3
4 2
9 8
*/