K Nearest Point

solution

code

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;


class point {
public:
    int x;
    int y;
    point(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};

point org(0, 0);

class myCompare {
public:
    bool operator () (point a, point b) const
    {
        return ((a.x-org.x)*(a.x-org.x) + (a.y-org.y)*(a.y-org.y)) > ((b.x-org.x)*(b.x-org.x) + (b.y-org.y)*(b.y-org.y));
    }
};

vector<point> kclosepoint(vector<point>& vec, int k, point o)
{
    org = o;
    priority_queue<point, vector<point>, myCompare> heap;
    vector<point> ret;

    int n = (int)vec.size();
    for(int i = 0; i<n; i++)
    {
        heap.push(vec[i]);   
    }

    while((int)ret.size() != k)
    {
        ret.push_back(heap.top());
        heap.pop();
    }

    return ret;
}


int main()
{
    vector<point> vec;
    point o(10, 10);
    vec.push_back(point(1, 2));
    vec.push_back(point(4, 5));
    vec.push_back(point(5, 6));
    vec.push_back(point(7, 7));
    vec.push_back(point(5, 5));

    vector<point> ret = kclosepoint(vec, 3, o);

    int n = (int)ret.size();
    for(int i = 0; i<n; i++)
    {
        cout<<ret[i].x<<" "<<ret[i].y<<endl;
    }

    return 1;
}