k近邻算法C++二维情况下的实现

k近邻算法C++二维实现

这是一个k近邻算法的二维实现（即K=2的情况）。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <cmath>

using namespace std;

const double inf = 1000.0;

const int maxn = ;

void debug_dfs(int);

void go_method();

bool should_go(int);

void dfs(int);

void back_method();

double Left[maxn], Right[maxn], Top[maxn], Button[maxn];

int tree[maxn][], parent[maxn], cnt = , n;

int depth[maxn];

struct point {

    double x, y;

};

vector<point> points[maxn];

queue<int> q;

point tmp[maxn];

point node[maxn];

point p0, anspoint;

int ansid;

double R;

bool cmpx(point a, point b) {

    return a.x < b.x;

}

bool cmpy(point a, point b) {

    return a.y < b.y;

}

int main() {

    scanf("%d", &n);

    point p;

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

        scanf("%lf%lf", &p.x , &p.y);

        points[cnt].push_back(p);

    }

    depth[cnt] = ;

    Left[cnt] = Button[cnt] = -inf;

    Right[cnt] = Top[cnt] = inf;

    parent[cnt] = -;

    q.push(cnt);

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        vector<point> &ps = points[u];

        int sz = ps.size();

        if(sz <= ) continue;

        if(sz == ) {

            node[u] = ps[];

            continue;

        }

        for(int i=;i<sz;i++) {

            tmp[i] = ps[i];

        }

        if(depth[u] %  == ) sort(tmp, tmp+sz, cmpx);

        else sort(tmp, tmp+sz, cmpy);

        int mid = sz / ;

        node[u] = tmp[mid];

        int lsz = mid, rsz = sz -  - mid;

        if(lsz) {

            int l = ++cnt;

            tree[u][] = l;

            parent[l] = u;

            depth[l] = depth[u] + ;

            q.push(l);

            for(int i=;i<mid;i++) points[l].push_back(tmp[i]);

            Left[l] = Left[u]; Right[l] = Right[u]; Top[l] = Top[u]; Button[l] = Button[u];

            if(depth[u] %  == ) Right[l] = tmp[mid].x;

            else Top[l] = tmp[mid].y;

        }

        if(rsz) {

            int r = ++cnt;

            tree[u][] = r;

            parent[r] = u;

            depth[r] = depth[u] + ;

            q.push(r);

            for(int i=mid+;i<sz;i++) points[r].push_back(tmp[i]);

            Left[r] = Left[u]; Right[r] = Right[u]; Top[r] = Top[u]; Button[r] = Button[u];

            if(depth[u] %  == ) Left[r] = tmp[mid].x;

            else Button[r] = tmp[mid].y;

        }

    }

    scanf("%lf%lf", &p0.x, &p0.y);

    back_method();

    printf("(%.2lf,%.2lf)\n", node[ansid].x, node[ansid].y);

    //debug_dfs(0);

    return ;

}

void go_method() {

    int cur = ;

    ansid = cur;

    while(true) {

        int l = tree[cur][], r = tree[cur][];

        if(l && Left[l] <= p0.x && Right[l] >= p0.x && Button[l] <= p0.y && Top[l] >= p0.y) {

            cur = l;

            ansid = l;

        } else if(r && Left[r] <= p0.x && Right[r] >= p0.x && Button[r] <= p0.y && Top[r] >= p0.y) {

            cur = r;

            ansid = r;

        } else {

            R = sqrt((p0.x-node[ansid].x)*(p0.x-node[ansid].x)+(p0.y-node[ansid].y)*(p0.y-node[ansid].y));

            return;

        }

    }

}

bool should_go(int u) {

    double dd, tt;

    dd = fabs(p0.x - Left[u]);

    if(dd < R) {

        tt = sqrt(R*R-dd*dd);

        if(p0.y-tt > Button[u] && p0.y-tt < Top[u]) return true;

        if(p0.y+tt > Button[u] && p0.y+tt < Top[u]) return true;

        if(Button[u] > p0.y-tt && Button[u] < p0.y+tt) return true;

        if(Top[u] > p0.y-tt && Top[u] < p0.y+tt) return true;

    }

    dd = fabs(p0.x - Right[u]);

    if(dd < R) {

        tt = sqrt(R*R-dd*dd);

        if(p0.y-tt > Button[u] && p0.y-tt < Top[u]) return true;

        if(p0.y+tt > Button[u] && p0.y+tt < Top[u]) return true;

        if(Button[u] > p0.y-tt && Button[u] < p0.y+tt) return true;

        if(Top[u] > p0.y-tt && Top[u] < p0.y+tt) return true;

    }

    dd = fabs(p0.y - Button[u]);

    if(dd < R) {

        tt = sqrt(R*R-dd*dd);

        if(p0.x-tt > Left[u] && p0.x+tt < Right[u]) return true;

        if(p0.x+tt > Left[u] && p0.x+tt < Right[u]) return true;

        if(Left[u] > p0.x-tt && Left[u] < p0.x+tt) return true;

        if(Right[u] > p0.x-tt && Right[u] < p0.x+tt) return true;

    }

    dd = fabs(p0.y - Top[u]);

    if(dd < R) {

        tt = sqrt(R*R-dd*dd);

        if(p0.x-tt > Left[u] && p0.x+tt < Right[u]) return true;

        if(p0.x+tt > Left[u] && p0.x+tt < Right[u]) return true;

        if(Left[u] > p0.x-tt && Left[u] < p0.x+tt) return true;

        if(Right[u] > p0.x-tt && Right[u] < p0.x+tt) return true;

    }

    return false;

}

void dfs(int u) {

    double _x = node[u].x, _y = node[u].y;

    double _r = sqrt((_x-p0.x)*(_x-p0.x)+(_y-p0.y)*(_y-p0.y));

    if(_r < R) {

        R = _r;

        ansid = u;

    }

    int l = tree[u][], r = tree[u][];

    if(l && should_go(l)) dfs(l);

    if(r && should_go(r)) dfs(r);

    return;

}

void back_method() {

    go_method();

    int cur = ansid, precur;

    while(cur != ) {

        precur = cur;

        cur = parent[cur];

        int l = tree[cur][], r = tree[cur][];

        if(precur == l && r && should_go(r)) dfs(r);

        else if(precur == r && l && should_go(l)) dfs(l);

    }

}

void debug_dfs(int u) {

    printf("dep[%d] = %d; (%.2lf,%.2lf); left:%.2lf,right:%.2lf,button:%.2lf,top:%.2lf\n",

            u, depth[u], node[u].x , node[u].y, Left[u], Right[u], Button[u], Top[u]);

    int l = tree[u][], r = tree[u][];

    if(l) debug_dfs(l);

    if(r) debug_dfs(r);

}