BZOJ 3053: The Closest M Points(K-D Tree)

来源:https://www.cnblogs.com/zwfymqz/archive/2018/05/22/9074473.html
-Advertisement-
Play Games

Description The course of Software Design and Development Practice is objectionable. ZLC is facing a serious problem .There are many points in K-dimen ...


Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1235  Solved: 418
[Submit][Status][Discuss]

Description

The course of Software Design and Development Practice is objectionable. ZLC is facing a serious problem .There are many points in K-dimensional space .Given a point. ZLC need to find out the closest m points. Euclidean distance is used as the distance metric between two points. The Euclidean distance between points p and q is the length of the line segment connecting them.In Cartesian coordinates, if p = (p1, p2,..., pn) and q = (q1, q2,..., qn) are two points in Euclidean n-space, then the distance from p to q, or from q to p is given by:
D(p,q)=D(q,p)=sqrt((q1-p1)^2+(q2-p2)^2+(q3-p3)^2…+(qn-pn)^2
Can you help him solve this problem?

 

 


軟工學院的課程很討厭!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,所以就麻煩你幫忙解決一下了……

【Input】

第一行,兩個非負整數:點數n(1 <= n <= 50000),和維度數k(1 <= k <= 5)。
接下來的n行,每行k個整數,代表一個點的坐標。
接下來一個正整數:給定的詢問數量t(1 <= t <= 10000)
下麵2*t行:
  第一行,k個整數:給定點的坐標
  第二行:查詢最近的m個點(1 <= m <= 10)

所有坐標的絕對值不超過10000。
有多組數據!

【Output】

對於每個詢問,輸出m+1行:
第一行:"the closest m points are:" m為查詢中的m
接下來m行每行代表一個點,按照從近到遠排序。

保證方案唯一,下麵這種情況不會出現:
2 2
1 1
3 3
1
2 2
1

 

 

Input

In the first line of the text file .there are two non-negative integers n and K. They denote respectively: the number of points, 1 <= n <= 50000, and the number of Dimensions,1 <= K <= 5. In each of the following n lines there is written k integers, representing the coordinates of a point. This followed by a line with one positive integer t, representing the number of queries,1 <= t <=10000.each query contains two lines. The k integers in the first line represent the given point. In the second line, there is one integer m, the number of closest points you should find,1 <= m <=10. The absolute value of all the coordinates will not be more than 10000.
There are multiple test cases. Process to end of file.

Output

For each query, output m+1 lines:
The first line saying :”the closest m points are:” where m is the number of the points.
The following m lines representing m points ,in accordance with the order from near to far
It is guaranteed that the answer can only be formed in one ways. The distances from the given point to all the nearest m+1 points are different. That means input like this:
2 2
1 1
3 3
1
2 2
1
will not exist.

Sample Input

3 2
1 1
1 3
3 4
2
2 3
2
2 3
1

Sample Output

the closest 2 points are:
1 3
3 4
the closest 1 points are:
1 3

HINT

 

Source

k-d tree

  真正意義上的的K-D Tree 就是把二維擴展到了$k$維 這樣只需要在建樹的時候按照維度迴圈建就可以了  
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1; 
    while(c < '0' || c > '9') {if(c == '-')f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, K, WD, root;
int out[MAXN];
struct Point {
    int x[6];
    bool operator < (const Point &rhs) const {
    return x[WD] < rhs.x[WD];
    }
}P[MAXN], ask;
#define ls(x) T[x].ls
#define rs(x) T[x].rs
struct KDTree {
    int mn[6], mx[6], ls, rs;
    Point tp;
}T[MAXN];
struct Ans {
    int val, ID;
    bool operator < (const Ans &rhs) const{
        return val < rhs.val;
    }
};
priority_queue<Ans>Q;
int sqr(int x) {
    return x * x;
}
void update(int k) {
    for(int i = 1; i <= K; i++) {
        T[k].mn[i] = T[k].mx[i] = T[k].tp.x[i];
        if(ls(k)) T[k].mn[i] = min(T[k].mn[i], T[ls(k)].mn[i]), T[k].mx[i] = max(T[k].mx[i], T[ls(k)].mx[i]);
        if(rs(k)) T[k].mn[i] = min(T[k].mn[i], T[rs(k)].mn[i]), T[k].mx[i] = max(T[k].mx[i], T[rs(k)].mx[i]);
    }
}
int Build(int l, int r, int wd) {
    WD = wd;
    if(l > r) return 0;
    int mid = l + r >> 1;
    nth_element(P + l, P + mid, P + r + 1);
    T[mid].tp = P[mid];
    T[mid].ls = Build(l, mid - 1, (wd + 1) % K);
    T[mid].rs = Build(mid + 1, r, (wd + 1) % K);
    update(mid);
    return mid;
}
int GetMinDis(Point a, KDTree b) {
    //if(b) return INF;
    int ans = 0;
    for(int i = 1; i <= K; i++)    {
        if(a.x[i] < b.mn[i]) ans += sqr(b.mn[i] - a.x[i]);
        if(a.x[i] > b.mx[i]) ans += sqr(a.x[i] - b.mx[i]);
    }
    return ans;
}
int Dis(Point a, Point b) {
    int ans = 0;
    for(int i = 1; i <= K; i++)
        ans += sqr(abs(a.x[i] - b.x[i]));
    return ans;
}
void Query(int k) {
    int ans = Dis(ask, T[k].tp);
    if(ans < Q.top().val) Q.pop(), Q.push((Ans){ans, k});
    int disl = INF, disr = INF;
    if(ls(k)) disl = GetMinDis(ask, T[ls(k)]);
    if(rs(k)) disr = GetMinDis(ask, T[rs(k)]);
    if(disl < disr) {
        if(disl < Q.top().val) Query(ls(k));
        if(disr < Q.top().val) Query(rs(k));
    }
    else {
        if(disr < Q.top().val) Query(rs(k));
        if(disl < Q.top().val) Query(ls(k));
    }
}
    
main() {
    while(scanf("%d %d", &N, &K) != EOF) {
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= K; j++)
                P[i].x[j] = read();
        root = Build(1, N, 0);
        int T = read();
        while(T--) {
            for(int i = 1; i <= K; i++) ask.x[i] = read();
            int M = read();
            printf("the closest %d points are:\n", M);
            for(int i = 1; i <= M; i++) Q.push((Ans){INF, 0});
            Query(root);
            for(int i = 1; i <= M; i++) 
                out[i] = Q.top().ID, Q.pop();
            for(int i = M; i >= 1; i--)
                for(int j = 1; j <= K; j++) 
                    printf("%d%c", P[out[i]].x[j], j != K ? ' ' : '\n');          
        }
    }
} 

 

 

 
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Django運算表達式與Q對象/F對象 1 模型查詢 概述: 1 查詢集:表示從資料庫中獲取的對象的集合 2 查詢集可以有多個過濾器,通過 邏輯運算符連接 3 過濾器就是一個函數,基於所給的參數限制查詢的結果,類似MySQL模糊查詢中where語句 4 查詢集等同select語句 2 查詢集 特點: ...
  • Python里的變數 門牌 Python在使用變數之前無須定義它的類型,但是必須聲明以及初始化該變數。 Python中給變數賦值就是聲明,初始化變數(也就是創建一個相應數據類型的對象,而那些數據類型就是類),變數的類型是取決於其儲存的數據。(下麵代碼中的a變數,其類型類型隨著賦值的類型不同而改變) ...
  • 1、網頁打開檢查器,到達該路徑,再刷新網頁,點擊第一個“Attractions”文件,出現headers(重要)、response、cookies等信息 2、定位元素位置方法,找唯一特征: 用滑鼠右鍵定位該元素的標簽位置,找出這類信息的唯一性屬性,最後用“標簽+屬性”的方式定位該欄位信息。如定點陣圖片 ...
  • 我在之前的隨筆中介紹了function如何保存參數,如何實現調用相關知識。對於一個函數對象或者函數指針來說,應該很容易理解。不過對於如何在function中保存類的成員函數,這個還是值得一說的。 還是按照之前的方式,通過boost的type_index,我們可以比較容易的知道function的父類是 ...
  • 二.安裝hibernate插件 打開eclipse,點擊help-->eclipse marketplace,如圖輸入:Hibernate Tools,再點擊Goa按鈕,找到JBoss Tools 點擊install安裝 如圖選擇Hibernate Tools,點擊Confrm安裝。安裝完成後重啟e ...
  • 本博客起源於博主的大三NoSQL課程設計,採用python+MongoDB結合方式,將數據從txt文件導入MongoDB之中,再將其取出以作圖。主要技術是採用python與MongoDB結合存儲讀取方案,所以本博客截取了課設的部分內容,主要講解python操作MongoDB方案實現,以給想要學習py ...
  • list是一種有序的集合,可以隨時添加和刪除其中的元素。 用len()函數可以獲得list元素的個數。 用索引來訪問list中每一個位置的元素,索引是從0開始的。如果要取最後一個元素,除了計算索引位置外,還可以用-1作索引,直接獲取最後一個元素。以此類推,可以獲取倒數第2個、倒數第3個。 list是 ...
  • 6.16.3 使用嵌套迴圈,按下麵格式列印字母: F FE FED FEDC FEDCB FEDCBA 1 #include <stdio.h> 2 3 int main() 4 { 5 const int ROWS = 6; 6 7 for (int row(0); row != ROWS; ++ ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...