HDU 5992 Finding Hotels

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5992

题意:二维平面上有一堆点,每个点都有自己的价值,现有若干查询,每次输出距离点(x,y)欧几里得距离最近的且价值不超过c的点。

思路:就是多带了一个价格限制的查询与(x,y)欧几里得距离最近的点,KDTree查询的时候要多带一个剪枝,也即当前区域的最小价值大于c的时候直接返回,不然会WA。。。至今没搞懂这个剪枝不加为什么就会WA。。。先留坑好了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define oo 999999999999999999LL
#define ls t[root].s[0]
#define rs t[root].s[1]
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=200000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
int T,n,m,D,root,x,y,price,ansindex;
ll ans;
struct P{
    int d[2],p,id;
    bool operator<(const P&rhs)const{
        return d[D]<rhs.d[D];
    }
}a[maxn];
struct _{
    int d[2],s[2],x[2],y[2],p,id,mn;
}t[maxn],Ans;
void umax(int&a,int b){if(a<b)a=b;}
void umin(int&a,int b){if(a>b)a=b;}
ll sqr(ll x){return x*x;}
ll getdis(int p){return sqr(max(max(x-t[p].x[1],t[p].x[0]-x),0))+sqr(max(max(y-t[p].y[1],t[p].y[0]-y),0));}
void maintain(int f,int x){
    umin(t[f].x[0],t[x].x[0]),umax(t[f].x[1],t[x].x[1]);
    umin(t[f].y[0],t[x].y[0]),umax(t[f].y[1],t[x].y[1]);
    umin(t[f].mn,t[x].mn);
}
int build(int l,int r,int d){
    D=d;int root=l+((r-l)>>1);
    nth_element(a+l,a+root,a+r+1);
    t[root].d[0]=t[root].x[0]=t[root].x[1]=a[root].d[0];
    t[root].d[1]=t[root].y[0]=t[root].y[1]=a[root].d[1];
    t[root].p=t[root].mn=a[root].p;
    t[root].id=a[root].id;
    if (l<root) ls=build(l,root-1,d^1),maintain(root,ls);
    if (root<r) rs=build(root+1,r,d^1),maintain(root,rs);
    return root;
}
void query(int root){
    if (t[root].mn>price) return;
    ll tmp=sqr(1LL*t[root].d[0]-x)+sqr(1LL*t[root].d[1]-y),d[2];
    if(ls)d[0]=getdis(ls);else d[0]=oo;
    if(rs)d[1]=getdis(rs);else d[1]=oo;
    if (tmp<ans && t[root].p<=price){
        ans=tmp;
        ansindex=root;
    }
    else if (tmp==ans && t[root].p<=price && t[ansindex].id>t[root].id){
        ansindex=root;
    }
    int flag=d[0]>=d[1];
    if (d[flag]<=ans) query(t[root].s[flag]);flag^=1;
    if (d[flag]<=ans) query(t[root].s[flag]);
}
int main(){
    for (read(T);T--;D=0,memset(t,0,sizeof(t))){
        read(n),read(m);
        for (int i=1;i<=n;i++) read(a[i].d[0]),read(a[i].d[1]),read(a[i].p),a[i].id=i;
        root=build(1,n,0);
        for (int i=1;i<=m;i++){
            read(x),read(y),read(price);
            ans=oo;
            ansindex=-1;
            query(root);
            printf("%d %d %d\n",t[ansindex].d[0],t[ansindex].d[1],t[ansindex].p);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注