Finding Hotels

The ﬁrst line is the number of test cases. For each test case, the ﬁrst line contains two integers N (N ≤ 200000) and M (M ≤ 20000). Each of the following N lines describes a hotel with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the hotel, c is its price. It is guaranteed that each of the N hotels has distinct x, distinct y, and distinct c. Then each of the following M lines describes the query of a guest with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the guest, c is the maximum acceptable price of the guest.

For each guests query, output the hotel that the price is acceptable and is nearest to the guests location. If there are multiple hotels with acceptable prices and minimum distances, output the ﬁrst one.

C++11(clang++ 3.9) 解法, 执行用时: 250ms, 内存消耗: 3932K, 提交时间: 2018-10-07 12:08:05

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mx = 2e5 + 10;
const ll inf = 1e18;
int n,m,ans;
ll z;
struct node
{
    int x,y;
    int c,id;
    bool operator < (node A)const
    {
        return x < A.x;
    }
}s[mx],Ts;
ll pows(ll x){  
    return x*x;  
}    
ll dist(node A,node    B)
{
    return pows(A.x-B.x)+pows(A.y-B.y);
}
ll divide(int l,int r)
{
    if(l==r){
        if(s[l].c>z) return inf;
        ans = l;
        return dist(s[l],Ts);
    }
    int mid = (l+r)>>1,X = s[mid].x;
    ll d;
    if(Ts.x<=X){
        d = divide(l,mid);
        for(int i=mid+1;i<=r;i++){
            if(pows(s[i].x-Ts.x)>d) break;
            if(s[i].c<=z){
                ll cost = dist(s[i],Ts);
                if(cost<d||(cost==d&&s[i].id<s[ans].id))
                ans = i,d = cost;
            }
        }
    }
    else{
         d = divide(mid+1,r);
        for(int i=mid;i>=l;i--){
            if(pows(s[i].x-Ts.x)>d) break;
            if(s[i].c<=z){
                ll cost = dist(s[i],Ts);
                if(cost<d||(cost==d&&s[i].id<s[ans].id))
                ans = i,d = cost;
            }
        }
    }
    return d;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].c);
            s[i].id = i;
        } 
        sort(s+1,s+1+n);
        while(m--){
            scanf("%d%d%d",&Ts.x,&Ts.y,&z);
            divide(1,n);
            printf("%d %d %d\n",s[ans].x,s[ans].y,s[ans].c);
        }
    }
    return 0;
}

详情