1. 首页
2. KDTree
3. 本页

HDU 5992 Finding Hotels (KD树)

题意：给出n个宾馆的坐标以及价格，现在有m个人要住宾馆，给出了m个的坐标和他们能承受的最高价格，询问在承受价格之内的最近的宾馆的坐标和价格，如果答案不唯一，输出顺序在前的宾馆。

思路：多了价值的限制条件，在同样满足条件的情况下，优先查询编号小的

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
#define pb push_back
#define Key_value ch[ch[root][1]][0]
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
const double eps=1e-6;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int M = 1000100;
const int MAXN =200010;
const int DIM=3;
inline LL sqr(LL x)
{
    return x*x;
}
namespace KDTree
{
int k;
struct Point
{
    int x[DIM];
    int pri;
    int id;
    LL distance(const Point &b)const
    {
        LL ret=0;
        for(int i=0; i<k; ++i)
            ret+=sqr((LL)x[i]-b.x[i]);
        return ret;
    }
};

struct cmpx
{
    int div;
    cmpx(const int &_div)
    {
        div=_div;
    }
    bool operator ()(const Point &a,const Point &b)
    {
        for(int i=0; i<k; ++i)
            if(a.x[(div+i)%k]!=b.x[(div+i)%k])
                return a.x[(div+i)%k]<b.x[(div+i)%k];
        return true;
    }
};
bool cmp(const Point &a,const Point &b,int div)
{
    cmpx cp=cmpx(div);
    return cp(a,b);
}
struct Node
{
    Point e;
    Node *lc,*rc;
    int div;
} pool[MAXN],*tail,*root;
void init()
{
    tail=pool;
}
Node* build(Point *a,int l,int r,int div)
{
    if(l>=r) return NULL;
    Node *p=tail++;
    p->div=div;
    int mid=(l+r)/2;
    nth_element(a+l,a+mid,a+r,cmpx(div));
    p->e=a[mid];
    p->lc=build(a,l,mid,(div+1)%k);
    p->rc=build(a,mid+1,r,(div+1)%k);
    return p;
}
Point ans;
void search(Point p,Node *x,int div,int m)
{
    if(!x) return;
    if(cmp(p,x->e,div) )
    {
        search(p,x->lc,(div+1)%k,m);
        if( ans.x[0]==-1 && x->e.pri<=p.pri)
        {
            ans=x->e;
        }
        else if( ans.x[0]!=-1 && p.distance(x->e) == p.distance(ans)  &&  x->e.pri<=p.pri  )
        {
            if(x->e.id<ans.id)
            {
                ans=x->e;
            }
        }
        else if(ans.x[0]!=-1 &&p.distance(x->e) < p.distance(ans)  &&  x->e.pri<=p.pri )
        {
            ans=x->e;
        }
        if( ans.x[0]==-1  || sqr(x->e.x[div]-p.x[div])< p.distance(ans)  )
            search(p,x->rc,(div+1)%k,m);
    }
    else
    {
        search(p,x->rc,(div+1)%k,m);
        if( ans.x[0]==-1 && x->e.pri<=p.pri)
        {
            ans=x->e;
        }
        else if( ans.x[0]!=-1 &&p.distance(x->e) == p.distance(ans)  &&  x->e.pri<=p.pri  )
        {
            if(x->e.id<ans.id)
            {
                ans=x->e;
            }
        }
        else if(ans.x[0]!=-1 && p.distance(x->e) < p.distance(ans)  &&  x->e.pri<=p.pri )
        {
            ans=x->e;
        }
        if(ans.x[0]==-1 || sqr(x->e.x[div]-p.x[div])< p.distance(ans) )
            search(p,x->lc,(div+1)%k,m);
    }
}
void search(Point p,int m=1)
{
    search(p,root,0,m);
}
};

KDTree::Point p[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        KDTree::k=2;
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<2; ++j)
            {
                scanf("%d",&p[i].x[j]);
            }
            scanf("%d",&p[i].pri);
            p[i].id=i;
        }
        KDTree::init();
        KDTree::root=KDTree::build(p,0,n,0);
        KDTree::Point tmp;
        while(m--)
        {
            for(int i=0; i<2; ++i)
                scanf("%d",&tmp.x[i]);
            scanf("%d",&tmp.pri);
            KDTree::ans.x[0]=-1;
            KDTree::search(tmp);
            printf("%d %d %d\n",KDTree::ans.x[0],KDTree::ans.x[1],KDTree::ans.pri);
        }
    }
    return 0;
}

/*
2
3 3
1 1 1
3 2 3
2 3 2
2 2 1
2 2 2
2 2 3
5 5
1 4 4
2 1 2
4 5 3
5 2 1
3 3 5
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5
*/