#include <iostream>

using namespace std;

struct Point {
  float x;
  float y;
  Point(float x, float y) : x(x), y(y) {};
};

struct DistPoint {
  float x;
  float y;
  float distance;
  DistPoint(float x, float y, float distance) : x(x), y(y), distance(distance) {};
};

struct DistPoint {
  Point* p;
  float distance;
  DistPoint(Point* p, float distance) : p(p), distance(distance) {};
};

// 1 4 2 9 3 2 N*MlogM (results are in order)

// 2 1 2 3 9 4 N*M (results are not in order)

// 1 2 2 9 3 4 N*k*logM - N*M*logk (results are in order)


vector<Point> KNearestNeighbors(const vector<Point>& map, const Point& query, const int k) {

    vector<DistPoint> distances;
    distances.reserve(map.size());
    for (const Point& p : map) {
        float distance = (p.x - query.x)*(p.x - query.x) + (p.y - query.y)*(p.y - query.y);
        distances.emplace_back(p.x, p.y, distance); // distances.emplace_back(&p, distance);
    }

    nth_element(distances.begin(), distances.begin() + k, distances.end(), [] (const DistPoint& p1, const DistPoint& p2) {
        return (p1.distance < p2.distance);
    });

    vector<Point> solution;
    solution.reserve(k);
    for (int i = 0; i < k; ++i)
        solution.emplace_back(distances[i].x, distances[i].y); // solution.emplace_back(*(distances[i].p));

    return solution;
}

int main()
{
    vector<Point> map_points{{}}; M

    Point query_point{}; N

    int k = 4;

    vector<Point> k_nearest_neighbors =  KNearestNeighbors(map_points, query_point, k);

    return 0;
}