The Closest M Points BZOJ 3053

The Closest M Points

【问题描述】

软工学院的课程很讨厌！ZLC同志遇到了一个头疼的问题：在K维空间里面有许多的点，对于某些给定的点，ZLC需要找到和它最近的m个点。

（这里的距离指的是欧几里得距离：D(p, q) = D(q, p) = sqrt((q1 - p1) ^ 2 + (q2 - p2) ^ 2 + (q3 - p3) ^ 2 + ... + (qn - pn) ^ 2)

ZLC要去打Dota，所以就麻烦你帮忙解决一下了……

【输入格式】

第一行，两个非负整数：点数n(1 <= n <= 50000)，和维度数k(1 <= k <= 5)。

接下来的n行，每行k个整数，代表一个点的坐标。

接下来一个正整数：给定的询问数量t(1 <= t <= 10000)

下面2*t行：

　　第一行，k个整数：给定点的坐标

　　第二行：查询最近的m个点(1 <= m <= 10)

所有坐标的绝对值不超过10000。

有多组数据！

【输出格式】

对于每个询问，输出m+1行：

第一行："the closest m points are:" m为查询中的m

接下来m行每行代表一个点，按照从近到远排序。

保证方案唯一，下面这种情况不会出现：

2 2

1 1

3 3

2 2

【样例输入】

3 2

1 1

1 3

3 4

2 3

【样例输出】

题解：

题意就是求与给定点第一近到第m近的点

用KD树查询

期望答案的计算：与给定点最近且不与给定点在同一块的期望点必定在边界上

开始时先将m个inf加入

那么当查询到的点与给定点的距离小于堆顶与给定点的距离时，就去掉堆顶并加入这个点

最后倒序输出

注意初始化（虽然没写什么初始化，但是要考虑一下的）

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 using namespace std;

 inline void Scan(int &x)

 {

     int o = ;

     char c;

     while((c = getchar()) < '' || c > '')

         if(c == '-') o = -;

     x = c - '';

     while((c = getchar()) >= '' && c <= '') x = x *  + c - '';

     x *= o;

 }

 const int me = ;

 const int inf = ;

 struct dot

 {

     int lc, rc;

     int dis;

     int v[], mi[], ma[];

 };

 dot point;

 dot c[me];

 dot tr[me];

 dot ans[me];

 struct name

 {

     int x;

     int dis;

 };

 inline bool operator < (const name &a, const name &b)

 {

     return a.dis < b.dis;

 }

 priority_queue <name> sta;

 int e, n, k, m;

 inline bool cmp(const dot &a, const dot &b)

 {

     return a.v[e] < b.v[e];

 }

 inline int Min(const int &x, const int &y)

 {

     return (x < y) ? x : y;

 }

 inline int Max(const int &x, const int &y)

 {

     return (x > y) ? x : y;

 }

 inline int Sqr(const int &x)

 {

     return x * x;

 }

 inline void Update(const int &x)

 {

     int l = tr[x].lc, r = tr[x].rc;

     for(int i = ; i < k; ++i)

     {

         tr[x].mi[i] = tr[x].ma[i] = tr[x].v[i];

         if(l) tr[x].mi[i] = Min(tr[x].mi[i], tr[l].mi[i]), tr[x].ma[i] = Max(tr[x].ma[i], tr[l].ma[i]);

         if(r) tr[x].mi[i] = Min(tr[x].mi[i], tr[r].mi[i]), tr[x].ma[i] = Max(tr[x].ma[i], tr[r].ma[i]);

     }

 }

 int Build(const int &l, const int &r, int d)

 {

     if(d >= k) d -= k;

     e = d;

     int mi = l + r >> ;

     nth_element(c + l, c + mi, c + r + , cmp);

     tr[mi] = c[mi];

     if(l < mi) tr[mi].lc = Build(l, mi - , d + );

     if(r > mi) tr[mi].rc = Build(mi + , r, d + );

     Update(mi);

     return mi;

 }

 inline int Dis(const int &x)

 {

     int sum = ;

     for(int i = ; i < k; ++i)

         sum += Sqr(tr[x].v[i] - point.v[i]);

     return sum;

 }

 inline int Get(const int &x)

 {

     int sum = ;

     for(int i = ; i < k; ++i)

     {

         if(point.v[i] < tr[x].mi[i]) sum += Sqr(tr[x].mi[i] - point.v[i]);

         if(point.v[i] > tr[x].ma[i]) sum += Sqr(point.v[i] - tr[x].ma[i]);

     }

     return sum;

 }

 void Ask(const int &x)

 {

     int dis = Dis(x);

     if(dis < sta.top().dis)

     {

         sta.pop();

         sta.push((name) {x, dis});

     }

     int le = inf, ri = inf;

     if(tr[x].lc) le = Get(tr[x].lc);

     if(tr[x].rc) ri = Get(tr[x].rc);

     if(le < ri)

     {

         if(le < sta.top().dis) Ask(tr[x].lc);

         if(ri < sta.top().dis) Ask(tr[x].rc);

     }

     else

     {

         if(ri < sta.top().dis) Ask(tr[x].rc);

         if(le < sta.top().dis) Ask(tr[x].lc);

     }

 }

 int main()

 {

 //    freopen("d.in", "r", stdin), freopen("d.out", "w", stdout);

     while(~scanf("%d", &n))

     {

         Scan(k);

         for(int i = ; i <= n; ++i)

             for(int j = ; j < k; ++j)

                 Scan(c[i].v[j]);

         int root = Build(, n, );

         int t;

         Scan(t);

         while(t--)

         {

             for(int i = ; i < k; ++i) Scan(point.v[i]);

             Scan(m);

             for(int i = ; i <= m; ++i) sta.push((name) {, inf});

             Ask(root);

             for(int i = ; i <= m; ++i)

             {

                 ans[i] = tr[sta.top().x];

                 sta.pop();

             }

             printf("the closest %d points are:\n", m);

             for(int i = m; i >= ; --i)

             {

                 for(int j = ; j < k - ; ++j)

                     printf("%d ", ans[i].v[j]);

                 printf("%d\n", ans[i].v[k - ]);

             }

         }

     }

 }

巴特西

The Closest M Points BZOJ 3053

最新文章

热门文章