hdu 5992(kdtree)
5569 ワード
Finding Hotels
Time Limit:2000/1000 MS(Java/Others) メモリLimit:102400/102400 K(Java/Others)Total Submission(s):1709 Acceepted Submission(s):529
Problem Description
The re are N hotels all over the world.Each hotel has a location and a price.M gusts want to find a hotel with an acceptable price and a minimum distance from their locations.The distance ares are meass.Euclidean tric.
Input
The first line is the number of test cases.For each test case,the first line contains two integers N(N≦20000)and M(M≦20000).Each of the following nline s describes a hotel with 3 integers x(ary)≦1It is its price.It isgaranteed that each of the N hotels distinct x、distinct y y、and distinct c.The n each of the follwing M lins describes the query of a gususest with 3 integersx x(1≦x≦x≦x≦N))(ininininininininininininininininininininininininininininininex x x x(1)(1))(1))))(1))))))(eeeeeey≦@@ininininininininininininininininininininininininininle price of the gust.
Output
For each gusts query,output the hotel that the price is acceptable and is nearst to the guses location.If there re multile hotels with acceptable press and minimum distancs,output the firsone.
Sample Input
Time Limit:2000/1000 MS(Java/Others) メモリLimit:102400/102400 K(Java/Others)Total Submission(s):1709 Acceepted Submission(s):529
Problem Description
The re are N hotels all over the world.Each hotel has a location and a price.M gusts want to find a hotel with an acceptable price and a minimum distance from their locations.The distance ares are meass.Euclidean tric.
Input
The first line is the number of test cases.For each test case,the first line contains two integers N(N≦20000)and M(M≦20000).Each of the following nline s describes a hotel with 3 integers x(ary)≦1It is its price.It isgaranteed that each of the N hotels distinct x、distinct y y、and distinct c.The n each of the follwing M lins describes the query of a gususest with 3 integersx x(1≦x≦x≦x≦N))(ininininininininininininininininininininininininininininininex x x x(1)(1))(1))))(1))))))(eeeeeey≦@@ininininininininininininininininininininininininininle price of the gust.
Output
For each gusts query,output the hotel that the price is acceptable and is nearst to the guses location.If there re multile hotels with acceptable press and minimum distancs,output the firsone.
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
题意：给出在二维坐标系中的n个点，每个点都有花费。接下来m个查询，每个查询给出二维坐标系中的一个点和容许最大花费c，要求在最大花费容许情况下求出距离查询的点最近的点，如果多个点距离相同，给出输入顺序中最前的一个点。
思路：kdtree，把二维坐标和花费组合为3个维度。
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 200005;
const ll INF = 1ll<<60;
struct node
{
int Min[3],Max[3]; //
int d[3]; //
int l,r; //
int id; //
}t[maxn];
int nowD; //
int x,y,c;
int ans; //
ll dist; //
ll getdist(int p) // p
{
if(t[p].Min[2]>c)return INF; // p
ll dis=0;
if(xt[p].Max[0]) dis+=1ll*(t[p].Max[0]-x)*(t[p].Max[0]-x);
if(yt[p].Max[1]) dis+=1ll*(t[p].Max[1]-y)*(t[p].Max[1]-y);
return dis;
}
bool cmp(node a,node b)
{
return a.d[nowD]t[now].Max[0]) t[now].Max[0]=t[t[now].l].Max[0];
if(t[t[now].l].Max[1]>t[now].Max[1]) t[now].Max[1]=t[t[now].l].Max[1];
if(t[t[now].l].Max[2]>t[now].Max[2]) t[now].Max[2]=t[t[now].l].Max[2];
if(t[t[now].l].Min[0]t[now].Max[0]) t[now].Max[0]=t[t[now].r].Max[0];
if(t[t[now].r].Max[1]>t[now].Max[1]) t[now].Max[1]=t[t[now].r].Max[1];
if(t[t[now].r].Max[2]>t[now].Max[2]) t[now].Max[2]=t[t[now].r].Max[2];
if(t[t[now].r].Min[0]>1;
nowD=D;
nth_element(t+l,t+mid,t+r+1,cmp);
if(l!=mid) t[mid].l=kd_build(l,mid-1,(D+1)%3);else t[mid].l=0;
if(r!=mid) t[mid].r=kd_build(mid+1,r,(D+1)%3);else t[mid].r=0;
t[mid].Max[0]=t[mid].Min[0]=t[mid].d[0];
t[mid].Max[1]=t[mid].Min[1]=t[mid].d[1];
t[mid].Max[2]=t[mid].Min[2]=t[mid].d[2];
kd_updata(mid);
return mid;
}
void kd_query(int p) //
{
ll dl=INF,dr=INF,d0=INF;
if(t[p].d[2]<=c) d0=1ll*(t[p].d[0]-x)*(t[p].d[0]-x)+1ll*(t[p].d[1]-y)*(t[p].d[1]-y);
if(d0'9')&&c!='-') c=getchar();
if(c=='-') q=1,c=getchar();
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
int main()
{
int cas;
int n,m;
cas=getint();
while(cas--)
{
n=getint();m=getint();
for(int i=1;i<=n;i++)
{
t[i].d[0]=getint();
t[i].d[1]=getint();
t[i].d[2]=getint();
t[i].id = i;
}
int rt = kd_build(1,n,0);
while(m--)
{
ans=0;
dist=INF;
x=getint();y=getint();c=getint();
kd_query(rt);
printf("%d %d %d
",t[ans].d[0],t[ans].d[1],t[ans].d[2]);
}
}
}