SHARE
TWEET

Untitled

bbescos Feb 23rd, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. struct Point {
  9.     int x;
  10.     int y;
  11.     int distance;
  12.     Point(int x, int y, int distance) : x(x), y(y), distance(distance) {}
  13. };
  14.  
  15. struct Compare {
  16.     bool operator() (Point p1, Point p2) {
  17.         return (p1.distance < p2.distance);
  18.     }
  19. } compare;
  20.  
  21. struct CompareMinHeap {
  22.     bool operator() (Point p1, Point p2) {
  23.         return (p1.distance > p2.distance);
  24.     }
  25. };
  26.  
  27. struct CompareMaxHeap {
  28.     bool operator() (Point p1, Point p2) {
  29.         return (p1.distance < p2.distance);
  30.     }
  31. };
  32.  
  33. // 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.
  34.  
  35. // Run-time complexity O(nlogn)
  36. /*
  37. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  38.    
  39.     vector<Point> distances;
  40.     // O(n)
  41.     for (int i = 0; i < points_set.size(); ++i) {
  42.         int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
  43.         Point np(points_set[i][0], points_set[i][1], dist);
  44.         distances.push_back(np);
  45.     }
  46.    
  47.     // O(nlogn) -- quick sort    
  48.     sort(distances.begin(), distances.end(), compare);
  49.    
  50.     vector<vector<int>> ans(k, vector<int> (2));
  51.     // O(k)
  52.     for (int i = 0; i < k; ++i) {
  53.         vector<int> p = {distances[i].x, distances[i].y};
  54.         ans[i] = p;
  55.     }
  56.    
  57.     return ans;
  58. }
  59. */
  60.  
  61. // Run-time complexity O(max(n, klogn)
  62. /*
  63. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  64.    
  65.     vector<Point> distances;
  66.     // O(n)
  67.     for (int i = 0; i < points_set.size(); ++i) {
  68.         int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
  69.         Point np(points_set[i][0], points_set[i][1], dist);
  70.         distances.push_back(np);
  71.     }
  72.    
  73.     // O(n)
  74.     priority_queue<Point, vector<Point>, CompareMinHeap> pq(distances.begin(), distances.end());
  75.    
  76.     vector<vector<int>> ans(k, vector<int> (2));
  77.     // O(klogn)
  78.     for (int i = 0; i < k; ++i) {
  79.         vector<int> p = {pq.top().x, pq.top().y};
  80.         ans[i] = p;
  81.         pq.pop(); //O(logn)
  82.     }
  83.    
  84.     return ans;
  85. }
  86. */
  87.  
  88. // Run-time complexity O(max(n, klogk, (n-k)logk)
  89. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  90.    
  91.     vector<Point> distances;
  92.     // O(n)
  93.     for (int i = 0; i < points_set.size(); ++i) {
  94.         int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
  95.         Point np(points_set[i][0], points_set[i][1], dist);
  96.         distances.push_back(np);
  97.     }
  98.    
  99.     // O(k)
  100.     priority_queue<Point, vector<Point>, CompareMaxHeap> pq(distances.begin(), distances.begin() + k);
  101.    
  102.     vector<vector<int>> ans(k, vector<int> (2));
  103.     // O((n-k)logk)
  104.     for (int i = k; i < points_set.size(); ++i) {
  105.         if (distances[i].distance < pq.top().distance) {
  106.             pq.pop();
  107.             pq.push(distances[i]);
  108.         }
  109.     }
  110.    
  111.     // O(klogk)
  112.     for (int i = 0; i < k; ++i) {
  113.         vector<int> p = {pq.top().x, pq.top().y};
  114.         ans[i] = p;
  115.         pq.pop(); //O(logk)
  116.     }
  117.    
  118.     return ans;
  119. }
  120.  
  121.  
  122. void PrintVector(const vector<vector<int>>& points_set) {
  123.  
  124.     for (int i = 0; i < points_set.size(); ++i) {
  125.         std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
  126.     }
  127. }
  128.  
  129. void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {
  130.    
  131.     int min_x = numeric_limits<int>::max();
  132.     int min_y = numeric_limits<int>::max();
  133.     int max_x = numeric_limits<int>::min();
  134.     int max_y = numeric_limits<int>::min();
  135.    
  136.     for (vector<int> point : points_set) {
  137.         if (point[0] < min_x)
  138.             min_x = point[0];
  139.         if (point[0] > max_x)
  140.             max_x = point[0];
  141.         if (point[1] > max_y)
  142.             max_y = point[1];
  143.         if (point[1] < min_y)
  144.             min_y = point[1];
  145.     }
  146.    
  147.     vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));
  148.    
  149.     for (int i = 0; i < grid.size(); ++i) {
  150.         for (int j = 0; j <grid[0].size(); ++j) {
  151.             for (vector<int> point : points_set) {
  152.                 if (point[0] == i && point[1] == j)
  153.                     grid[i][j] = 'x';
  154.             }
  155.             if (p[0] == i && p[1] == j)
  156.                 grid[i][j] = 'o';
  157.         }
  158.     }
  159.    
  160.     for (int i = 0; i < grid.size(); ++i) {
  161.         for (int j = 0; j < grid[0].size(); ++j) {
  162.             std::cout << grid[i][j] << " ";
  163.         }
  164.         std::cout << std::endl;
  165.     }
  166.    
  167. }
  168.  
  169. int main()
  170. {
  171.     vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};
  172.    
  173.     vector<int> p{2, 4};
  174.  
  175.     int k = 3;
  176.    
  177.     vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);
  178.  
  179.     PrintGrid(points_set, p);
  180.  
  181.     PrintVector(kpoints_set);
  182.  
  183.     return 0;
  184. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top