这坑爹玩意……这样能删能插了。。
ps:我居然把分裂点看反了！！
pps:删除节点之后我居然忘记上传了！！（虽然按照这颗树的尿性很快就会上传上去。。）
代码有错……nth_element是左闭右开的
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const double eps=1e-12;
const int poolsize = 10000;
const double alpha = 0.7;
class kdtree
{
public:
struct pointF
{
double d[2];
inline bool operator == (const pointF &a){
return (abs(a.d[0]-d[0])<=eps && abs(a.d[1]-d[1])<=eps);
}
};
private:
struct node
{
kdtree *t;
pointF split_node;
int split_method;
node*ch[2];
node*left(){return ch[0];}; // < split_pos
node*right(){return ch[1];};// > split_pos
int size;
bool exist;
void rebuild();
void rebuild_dfs(node *n,pointF* ps,int &size);
bool judge(){
if (!ch[0]||!ch[1]) return false;
return !size || ch[0]->size > alpha * size || ch[1]->size > alpha * size;
};
node(){
size=1;
exist=true;
//if (judge()) rebuild();
}
}*top,node_pool[poolsize],*alloca_reuse[poolsize];int pool;int stack_size;
node * alloca_node(){
if (stack_size){
// 优先从回收池中取出
node_pool[stack_size].t = this;node_pool[stack_size].size=1;node_pool[stack_size].exist=true;
return alloca_reuse[stack_size--];
}
else
{
node_pool[pool].t = this;node_pool[pool].size=1;node_pool[pool].exist=true;
return &node_pool[pool++];
}
};
void release_node(node *n){
memset(n,0,sizeof(node));
alloca_reuse[stack_size++]=n;
};
public:
void build(pointF *_ps,int _size); // ps => [1,n]
pointF search(pointF x);
kdtree(){
top=0;pool=0;ps=0;builded=false;sort_by=0;stack_size=0;
memset(node_pool,0,sizeof(node_pool));
memset(alloca_reuse,0,sizeof(alloca_reuse));
};
void clean(){
top=0;pool=0;ps=0;builded=false;sort_by=0;stack_size=0;
memset(node_pool,0,sizeof(node_pool));
memset(alloca_reuse,0,sizeof(alloca_reuse));
};
void clean_fast(){
top=0;pool=0;ps=0;n=0;builded=false;sort_by=0;stack_size=0;
memset(node_pool,0,sizeof(node_pool));
memset(alloca_reuse,0,sizeof(alloca_reuse));
};
bool remove(pointF p);
void insert(pointF p);
void select(pointF lt,pointF rb,vector<pointF> &target);
private:
pointF *ps;
pointF filter;
pointF result;
bool builded;
int n;
node* build_dfs(int l,int r);
void search_dfs(node* n,bool force,bool lazy);
void insert_dfs(node* n,bool mt,bool re_lazy);
void select_dfs(node* n,pointF <,pointF& rb,vector<pointF> &target);
node *ansp;
double ansd;
inline double Variance(int l,int r,int d){
double variance = 0;
double Average = 0;
for (int i=l;i<=r;i++) Average+=ps[i].d[d];
Average/=(r-l+1.0);
for (int i=l;i<=r;i++) variance+=(ps[i].d[d]-Average)*(ps[i].d[d]-Average);
variance/=(r-l+1.0);
return variance;
};
int sort_by;
class sort_compare{
private:
int sort_by;
public:
bool operator()(const pointF & x, const pointF & y){
return x.d[sort_by]<y.d[sort_by];
};
sort_compare(int _sort_by){
sort_by=_sort_by;
}
};
inline double distance(const pointF & x,const pointF & y){
return (x.d[0]-y.d[0])*(x.d[0]-y.d[0]) + (x.d[1]-y.d[1])*(x.d[1]-y.d[1]);
}
}T;
void kdtree::build(pointF *_ps,int _size){
if (builded) throw "Cannot build a kd-tree again before you clean it!!";
builded=true;
ps=_ps;n=_size;
top=build_dfs(1,n);
};
kdtree::node* kdtree::build_dfs(int l,int r){ // [l,r]
if (r-l<0) return NULL;
node * range = alloca_node();range->exist=true;
int mid = (l+r)>>1;
double VarianceX = Variance(l,r,0);
double VarianceY = Variance(l,r,1);
int split_method_i = VarianceY>VarianceX;
range->split_method = split_method_i;
sort_by = split_method_i;
nth_element(ps+l,ps+mid,ps+r+1,sort_compare(sort_by));
//sort(ps+l,ps+r,sort_compare(sort_by));
range->split_node = *(ps+mid);
range->ch[0]= build_dfs(l,mid-1);
range->ch[1]= build_dfs(mid+1,r);
range->size = ((range->ch[0])?(range->ch[0]->size):(0))+((range->ch[1])?(range->ch[1]->size):(0)) + (range->exist);
return range;
};
kdtree::pointF kdtree::search(pointF x){
if (!builded) throw "Cannot work on empty tree!!";
filter=x;
ansd = 1e307;
search_dfs(top,false,false);
return ansp->split_node;
};
bool kdtree::remove(pointF x){
/* 刚调整过，本来删完忘记上传size修改了，这样应该可以……
* 但是一次修改造成的不平衡只有下次访问到才会修复……
*/
if (!builded) throw "Cannot work on empty tree!!";
filter=x;
ansd = 1e307;
search_dfs(top,true,false);
return ansd==0;
}
void kdtree::search_dfs(node* n,bool force,bool lazy){
if (!n) return ;
double dist=0;
dist =distance(n->split_node,filter);
if ((dist<ansd && n->exist && !force) || (force && n->split_node==filter)){
ansd=dist;
ansp=n;
if (force) {
ansp->exist=false;
ansp->size--;
return;
}
}
int sm=n->split_method;
bool rebuild=n->judge();
double radius = (filter.d[sm]-n->split_node.d[sm])*(filter.d[sm]-n->split_node.d[sm]);
if (filter.d[sm]-n->split_node.d[sm]<=eps){
// left
search_dfs(n->ch[0],force,lazy|rebuild);
if (ansd<=radius) search_dfs(n->ch[1],force,lazy|rebuild);
}else{
// right
search_dfs(n->ch[1],force,lazy|rebuild);
if (ansd<=radius) search_dfs(n->ch[0],force,lazy|rebuild);
}
n->size = ((n->ch[0])?(n->ch[0]->size):(0))+((n->ch[1])?(n->ch[1]->size):(0)) + (n->exist);
if (rebuild &!lazy) n->rebuild(); // 重构这棵树
}
void kdtree::insert(pointF p){
filter = p;
insert_dfs(top,0,0);
}
void kdtree::insert_dfs(node* n,bool mt,bool re_lazy){
/*
* 同样……一次修改之后不会马上重构。。
*/
int sm=n->split_method;
double radius = (filter.d[sm]-n->split_node.d[sm])*(filter.d[sm]-n->split_node.d[sm]);
bool re=n->judge();
int belong = (filter.d[sm]-n->split_node.d[sm]>=eps); //target.pos>split => 1
if (n->ch[belong]!=NULL){
insert_dfs(n->ch[belong],!mt,re|re_lazy);
}else{
n->ch[belong]=alloca_node();
n->ch[belong]->split_method = mt;
n->ch[belong]->split_node = filter;
}
n->size = ((n->ch[0])?(n->ch[0]->size):(0))+((n->ch[1])?(n->ch[1]->size):(0)) + (n->exist);
if (!re_lazy && re) n->rebuild();
};
void kdtree::node::rebuild(){
int size=1;
rebuild_dfs(this,t->ps,size);size--;
node *va = t->build_dfs(1,size);
memcpy(this,va,sizeof(node));
t->release_node(va);
};
void kdtree::node::rebuild_dfs(node *n,pointF* ps,int &size){
if (!n) return;
if (n->exist){
ps[size++]=n->split_node;
}
rebuild_dfs(n->ch[0],ps,size);
rebuild_dfs(n->ch[1],ps,size);
if (n!=this) t->release_node(n);
};
void kdtree::select(pointF lt,pointF rt,vector<pointF> &target){
select_dfs(top,lt,rt,target);
};
void kdtree::select_dfs(node* n,pointF <,pointF &rb,vector<pointF> &target){
/*
* 关于这里的lt、rb或许重构为degree的范围更好？
*/
if (!n) return;
if (n->size==0) return ;
pointF p = n->split_node;
if (n->exist && p.d[0]>=lt.d[0] && // 大于左上的x
p.d[0]<=rb.d[0] && // 小于右下的x
p.d[1]<=lt.d[1] && // 小于左上的y
p.d[1]>=rb.d[1]) // 大于右下的y
target.push_back(p);
if (n->split_method==0){
if (lt.d[0] <= p.d[0]) select_dfs(n->ch[0],lt,rb,target); // left
if (rb.d[0] >= p.d[0]) select_dfs(n->ch[1],lt,rb,target); // right
} else {
if (rb.d[1] <= p.d[1]) select_dfs(n->ch[0],lt,rb,target); // bottom
if (lt.d[1] >= p.d[1]) select_dfs(n->ch[1],lt,rb,target); // top
}
};
kdtree::pointF points[500]; // buffers
int main(){
int n,q;
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++) scanf("%lf%lf",&points[i].d[0],&points[i].d[1]);
T.build(points,n);
while (q--){
kdtree::pointF lt;
kdtree::pointF rt;
int x;scanf("%d",&x);
if (x==1){
scanf("%lf%lf",<.d[0],<.d[1]);
scanf("%lf%lf",&rt.d[0],&rt.d[1]);
vector<kdtree::pointF> v;
T.select(lt,rt,v);
for (vector<kdtree::pointF>::iterator it=v.begin();it!=v.end();it++)
printf("(%.2lf %.2lf)\n",it->d[0],it->d[1]);
}else{
scanf("%lf%lf",<.d[0],<.d[1]);
if (x==2)
T.remove(lt);
else
T.insert(lt);
}
}
system("pause");
};
