bzoj2626 JZPFAR

bzoj2626 JZPFAR

​​‎ Description 　　平面上有n个点。现在有m次询问，每次给定一个点(px, py)和一个整数k，输出n个点中离(px, py)的距离第k大的点的标号。如果有两个(或多个)点距离(px, py)相同，那么认为标号较小的点距离较大。 Input 　　第一行，一个整数n，表示点的个数。 下面n行，每行两个整数x_i, y_i，表示n个点的坐标。点的标号按照输入顺序，分别为1..n。 下面一行，一个整数m，表示询问个数。 下面m行，每行三个整数px_i, py_i, k_i，表示一个询问。 Output 　　m行，每行一个整数，表示相应的询问的答案。 Sample Input 3 0 0 0 1 0 2 3 1 1 2 0 0 3 0 1 1

Sample Output 3 1 1

数据规模和约定 50%的数据中，n个点的坐标在某范围内随机分布。 100%的数据中，n<=10^5, m<=10^4, 1<=k<=20，所有点(包括询问的点)的坐标满足绝对值<=10^9，n个点中任意两点坐标不同，m个询问的点的坐标在某范围内随机分布。

仔细算了发 似乎最坏情况会炸long long 但我觉得sqrt影响效率和精度 就没写 似乎也A了 大概是裸的kd-tree 估价函数也比较好写 但是样例提示我们需要注意一下几点问题 1、 有可能存在距离相同但是编号比较小的情况这种情况我们不能直接跳过 而是也应该进去暴力算一算2、在定义小根堆的时候由于priority_queue内部是仍然是按照大根堆来搞 那么由于我应该只可以重载小于号 所以我需要在重载小于号的时候反向即可 其他就是一些常数的优化了 具体可以看下代码 比如我算下左右子树最远的距离 哪个更远去搞那个因为可能搞完这个 另一棵都不用搞了 这题要求维护最远的k点那么我需要维护一个小根堆 每次比较下 如果我比最小的还小就不搞了 对于每个节点 如果我比最小的大就去搞一搞 同时为了避免queue empty一开始我预处理的放入k个非常小的即可

#include#include#include#include#include#include#define N 110000#define inf 1LL<<60#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; }inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}int D,n,m,root,k;struct node1{ int d[2],id; int& operator[](int x){return d[x];} friend bool operator<(node1 a,node1 b){return a[D]b.dis; }};inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].idmin=min(tree[x].x.id,min(tree[l].idmin,tree[r].idmin)); for (int i=0;i<2;++i) tree[x].max[i]=max(tree[x].max[i],max(tree[l].max[i],tree[r].max[i])); for (int i=0;i<2;++i) tree[x].min[i]=min(tree[x].min[i],min(tree[l].min[i],tree[r].min[i]));}inline void build(int &x,int l,int r,int dim){ int mid=l+r>>1;x=mid;D=dim;nth_element(point+l,point+mid,point+r+1); tree[x].x=point[mid];for (int i=0;i<2;++i) tree[x].min[i]=tree[x].max[i]=point[mid][i]; if (lmid) build(tree[x].right,mid+1,r,dim^1);update(x);}inline ll calc(node1 a){ return (ll)(a[0]-P[0])*(a[0]-P[0])+(ll)(a[1]-P[1])*(a[1]-P[1]);}priority_queueq;inline ll calc1(int x){ ll tmp=0; for (int i=0;i<2;++i){ ll tmp1=max(abs(P[i]-tree[x].min[i]),abs(P[i]-tree[x].max[i])); tmp+=tmp1*tmp1; }return tmp; }inline void query(int x){ ll dis=calc(tree[x].x),ldis=-inf,rdis=-inf;int id=tree[x].x.id; if (dis>q-().dis||(dis==q-().dis&&idrdis){ if (ldis>q-().dis||(ldis==q-().dis&&tree[tree[x].left].idminq-().dis||(rdis==q-().dis&&tree[tree[x].right].idminq-().dis||(rdis==q-().dis&&tree[tree[x].right].idminq-().dis||(ldis==q-().dis&&tree[tree[x].left].idmin

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。