/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Point {
    int x;
    int y;
    int distance;
    Point(int x, int y, int distance) : x(x), y(y), distance(distance) {}
};

struct Compare {
    bool operator() (Point p1, Point p2) {
        return (p1.distance < p2.distance);
    }
} compare;

struct CompareMinHeap {
    bool operator() (Point p1, Point p2) {
        return (p1.distance > p2.distance);
    }
};

struct CompareMaxHeap {
    bool operator() (Point p1, Point p2) {
        return (p1.distance < p2.distance);
    }
};

// Given a point P and other N points in two dimensional space, find K points out of the N points which are nearest to P.

// Run-time complexity O(nlogn)
/*
vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {

    vector<Point> distances;
    // O(n)
    for (int i = 0; i < points_set.size(); ++i) {
        int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
        Point np(points_set[i][0], points_set[i][1], dist);
        distances.push_back(np);
    }

    // O(nlogn) -- quick sort
    sort(distances.begin(), distances.end(), compare);

    vector<vector<int>> ans(k, vector<int> (2));
    // O(k)
    for (int i = 0; i < k; ++i) {
        vector<int> p = {distances[i].x, distances[i].y};
        ans[i] = p;
    }

    return ans;
}
*/

// Run-time complexity O(max(n, klogn)
/*
vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {

    vector<Point> distances;
    // O(n)
    for (int i = 0; i < points_set.size(); ++i) {
        int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
        Point np(points_set[i][0], points_set[i][1], dist);
        distances.push_back(np);
    }

    // O(n)
    priority_queue<Point, vector<Point>, CompareMinHeap> pq(distances.begin(), distances.end());

    vector<vector<int>> ans(k, vector<int> (2));
    // O(klogn)
    for (int i = 0; i < k; ++i) {
        vector<int> p = {pq.top().x, pq.top().y};
        ans[i] = p;
        pq.pop(); //O(logn)
    }

    return ans;
}
*/

// Run-time complexity O(max(n, klogk, (n-k)logk)
/*
vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {

    vector<Point> distances;
    // O(n)
    for (int i = 0; i < points_set.size(); ++i) {
        int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
        Point np(points_set[i][0], points_set[i][1], dist);
        distances.push_back(np);
    }

    // O(k)
    priority_queue<Point, vector<Point>, CompareMaxHeap> pq(distances.begin(), distances.begin() + k);

    vector<vector<int>> ans(k, vector<int> (2));
    // O((n-k)logk)
    for (int i = k; i < points_set.size(); ++i) {
        if (distances[i].distance < pq.top().distance) {
            pq.pop();
            pq.push(distances[i]);
        }
    }

    // O(klogk)
    for (int i = 0; i < k; ++i) {
        vector<int> p = {pq.top().x, pq.top().y};
        ans[i] = p;
        pq.pop(); //O(logk)
    }

    return ans;
}
*/

void PrintVector(const vector<Point>& vec) {
    for (Point p : vec) {
        std::cout << p.distance << " ";
    }
    std::cout << std::endl;
}

/*void HoareQuickSort(vector<Point>& vec, int left, int right, const int k) {

    if (k <= right - left + 1) {

        Point pivot = vec[right];
        int j = left - 1;
        for (int i = left; i <= right - 1; ++i) {
            if (vec[i].distance < pivot.distance)
                swap(vec[i], vec[++j]);
        }
        swap(vec[++j], vec[right]);

        PrintVector(vec);

        if (j - left == k - 1)
            return;
        if (j - left > k - 1)
            HoareQuickSort(vec, left, j - 1, k);

        HoareQuickSort(vec, j + 1, right, k - j + left - 1);
    }

    return;
}*/

// Run-time complexity O(n)
vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {

    vector<Point> distances;
    // O(n)
    for (int i = 0; i < points_set.size(); ++i) {
        int dist = (points_set[i][0] - p[0])*(points_set[i][0] - p[0]) + (points_set[i][1] - p[1])*(points_set[i][1] - p[1]);
        Point np(points_set[i][0], points_set[i][1], dist);
        distances.push_back(np);
    }

    // O(n)
    nth_element(distances.begin(), distances.begin() + k, distances.end(), [](Point i, Point j){return (i.distance < j.distance);});

    vector<vector<int>> ans(k, vector<int> (2));
    // O(k)
    for (int i = 0; i < k; ++i) {
        vector<int> v = {distances[i].x, distances[i].y};
        ans[i] = v;
    }

    return ans;
}

void PrintVector(const vector<vector<int>>& points_set) {

    for (int i = 0; i < points_set.size(); ++i) {
        std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
    }
}

void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {

    int min_x = numeric_limits<int>::max();
    int min_y = numeric_limits<int>::max();
    int max_x = numeric_limits<int>::min();
    int max_y = numeric_limits<int>::min();

    for (vector<int> point : points_set) {
        if (point[0] < min_x)
            min_x = point[0];
        if (point[0] > max_x)
            max_x = point[0];
        if (point[1] > max_y)
            max_y = point[1];
        if (point[1] < min_y)
            min_y = point[1];
    }

    vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));

    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j <grid[0].size(); ++j) {
            for (vector<int> point : points_set) {
                if (point[0] == i && point[1] == j)
                    grid[i][j] = 'x';
            }
            if (p[0] == i && p[1] == j)
                grid[i][j] = 'o';
        }
    }

    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            std::cout << grid[i][j] << " ";
        }
        std::cout << std::endl;
    }

}

int main()
{
    vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};

    vector<int> p{2, 4};

    int k = 4;

    vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);

    PrintGrid(points_set, p);

    PrintVector(kpoints_set);

    return 0;
}