Finding Hotels
2024-10-20 22:48:49
Finding Hotels
http://acm.hdu.edu.cn/showproblem.php?pid=5992
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 2180 Accepted Submission(s): 688
Problem Description
There are N hotels all over the world. Each hotel has a location and a price. M guests want to find a hotel with an acceptable price and a minimum distance from their locations. The distances are measured in Euclidean metric.
Input
The first line is the number of test cases. For each test case, the first 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.
Output
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 first one.
Sample Input
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
Sample Output
1 1 1
2 3 2
3 2 3
5 2 1
2 1 2
2 1 2
1 4 4
3 3 5
Source
结构体内用友元函数这题会T....
模板题
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 200005
using namespace std; int n,m,id;//n是点数,m是维度,id是当前切的维度 struct sair{
long long p[];
bool operator<(const sair &b)const{
return p[id]<b.p[id];
}
}_data[N],data[N<<],tt[N];
int flag[N<<]; priority_queue<pair<long long,sair> >Q; void build(int l,int r,int rt,int dep){
if(l>r) return;
flag[rt]=;
flag[rt<<]=flag[rt<<|]=-;
id=dep%m;
int mid=l+r>>;
nth_element(_data+l,_data+mid,_data+r+);
data[rt]=_data[mid];
build(l,mid-,rt<<,dep+);
build(mid+,r,rt<<|,dep+);
} void query(sair p,int k,int rt,int dep){
if(flag[rt]==-) return;
pair<long long,sair> cur(,data[rt]);//获得当前节点
for(int i=;i<m;i++){//计算当前节点到P点的距离
cur.first+=(cur.second.p[i]-p.p[i])*(cur.second.p[i]-p.p[i]);
}
int idx=dep%m;
int fg=;
int x=rt<<;
int y=rt<<|;
if(p.p[idx]>=data[rt].p[idx]) swap(x,y);
if(~flag[x]) query(p,k,x,dep+);
//开始回溯
if(Q.size()<k){
if(cur.second.p[]<=p.p[]){
Q.push(cur);
}
fg=;
}
else{
if(cur.first<=Q.top().first&&cur.second.p[]<=p.p[]){
if(cur.first==Q.top().first){
if(cur.second.p[]<Q.top().second.p[]){
Q.pop();
Q.push(cur);
}
}
else{
Q.pop();
Q.push(cur);
}
}
if(((p.p[idx]-data[rt].p[idx])*(p.p[idx]-data[rt].p[idx]))<Q.top().first){
fg=;
}
}
if(~flag[y]&&fg){
query(p,k,y,dep+);
}
} sair ans; int main(){
int T;
scanf("%d",&T);
int k;
while(T--){
scanf("%d %d",&n,&k);
m=;
for(int i=;i<=n;i++){
scanf("%lld %lld %lld",&_data[i].p[],&_data[i].p[],&_data[i].p[]);
_data[i].p[]=i;
}
build(,n,,);
sair tmp;
for(int i=;i<=k;i++){
while(!Q.empty()){
Q.pop();
}
scanf("%lld %lld %lld",&tmp.p[],&tmp.p[],&tmp.p[]);
tmp.p[]=0x3f3f3f3f;
query(tmp,,,);
ans=Q.top().second;
Q.pop();
printf("%lld %lld %lld\n",ans.p[],ans.p[],ans.p[]);
}
}
}
最新文章
- vs代码段快捷键设置
- [SAP ABAP开发技术总结]权限对象检查
- Xcode 的正确打开方式——Debugging(转载)
- jQuery实现跨域访问
- [转] C#中的Dictionary的使用
- C# 中的 null
- serialize
- scrollbarsstyle
- Microsoft.AlphaImageLoader滤镜讲--透明处理<;转>;
- 使用WPF创建无边框窗体
- 云端TensorFlow读取数据IO的高效方式
- c++/cmake /Android NDK 动态链接库交叉编译笔记
- 网络基础Cisco路由交换四
- elasticsearch kabana中创建索引
- 初学ubuntu之文件权限权限
- codevs 1080 线段树练习(线段树)
- ABAP开发需要养成的习惯—程序修改数据库表
- iOS.Location-Based Service
- zookeeper 启动脚本
- 行为类模式(五):中介者(Mediator)