SHARE
TWEET

Untitled

bbescos Feb 23rd, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. struct Point {
  17.     int x;
  18.     int y;
  19.     int distance;
  20.     Point(int x, int y, int distance) : x(x), y(y), distance(distance) {}
  21. };
  22.  
  23. struct Compare {
  24.     bool operator() (Point p1, Point p2) {
  25.         return (p1.distance < p2.distance);
  26.     }
  27. } compare;
  28.  
  29. struct CompareMinHeap {
  30.     bool operator() (Point p1, Point p2) {
  31.         return (p1.distance > p2.distance);
  32.     }
  33. };
  34.  
  35. struct CompareMaxHeap {
  36.     bool operator() (Point p1, Point p2) {
  37.         return (p1.distance < p2.distance);
  38.     }
  39. };
  40.  
  41. // 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.
  42.  
  43. // Run-time complexity O(nlogn)
  44. /*
  45. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  46.    
  47.     vector<Point> distances;
  48.     // O(n)
  49.     for (int i = 0; i < points_set.size(); ++i) {
  50.         int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
  51.         Point np(points_set[i][0], points_set[i][1], dist);
  52.         distances.push_back(np);
  53.     }
  54.    
  55.     // O(nlogn) -- quick sort    
  56.     sort(distances.begin(), distances.end(), compare);
  57.    
  58.     vector<vector<int>> ans(k, vector<int> (2));
  59.     // O(k)
  60.     for (int i = 0; i < k; ++i) {
  61.         vector<int> p = {distances[i].x, distances[i].y};
  62.         ans[i] = p;
  63.     }
  64.    
  65.     return ans;
  66. }
  67. */
  68.  
  69. // Run-time complexity O(max(n, klogn)
  70. /*
  71. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  72.    
  73.     vector<Point> distances;
  74.     // O(n)
  75.     for (int i = 0; i < points_set.size(); ++i) {
  76.         int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
  77.         Point np(points_set[i][0], points_set[i][1], dist);
  78.         distances.push_back(np);
  79.     }
  80.    
  81.     // O(n)
  82.     priority_queue<Point, vector<Point>, CompareMinHeap> pq(distances.begin(), distances.end());
  83.    
  84.     vector<vector<int>> ans(k, vector<int> (2));
  85.     // O(klogn)
  86.     for (int i = 0; i < k; ++i) {
  87.         vector<int> p = {pq.top().x, pq.top().y};
  88.         ans[i] = p;
  89.         pq.pop(); //O(logn)
  90.     }
  91.    
  92.     return ans;
  93. }
  94. */
  95.  
  96. // Run-time complexity O(max(n, klogk, (n-k)logk)
  97. /*
  98. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  99.    
  100.     vector<Point> distances;
  101.     // O(n)
  102.     for (int i = 0; i < points_set.size(); ++i) {
  103.         int dist = abs(points_set[i][0] - p[0]) + abs(points_set[i][1] - p[1]);
  104.         Point np(points_set[i][0], points_set[i][1], dist);
  105.         distances.push_back(np);
  106.     }
  107.    
  108.     // O(k)
  109.     priority_queue<Point, vector<Point>, CompareMaxHeap> pq(distances.begin(), distances.begin() + k);
  110.    
  111.     vector<vector<int>> ans(k, vector<int> (2));
  112.     // O((n-k)logk)
  113.     for (int i = k; i < points_set.size(); ++i) {
  114.         if (distances[i].distance < pq.top().distance) {
  115.             pq.pop();
  116.             pq.push(distances[i]);
  117.         }
  118.     }
  119.    
  120.     // O(klogk)
  121.     for (int i = 0; i < k; ++i) {
  122.         vector<int> p = {pq.top().x, pq.top().y};
  123.         ans[i] = p;
  124.         pq.pop(); //O(logk)
  125.     }
  126.    
  127.     return ans;
  128. }
  129. */
  130.  
  131. void PrintVector(const vector<Point>& vec) {
  132.     for (Point p : vec) {
  133.         std::cout << p.distance << " ";
  134.     }
  135.     std::cout << std::endl;
  136. }
  137.  
  138. void HoareQuickSort(vector<Point>& vec, int left, int right, const int k) {
  139.    
  140.     if (k <= right - left + 1) {
  141.        
  142.         Point pivot = vec[right];
  143.         int j = -1;
  144.         for (int i = 0; i < vec.size() - 1; ++i) {
  145.             if (vec[i].distance < pivot.distance)
  146.                 swap(vec[i], vec[++j]);
  147.         }
  148.         swap(vec[++j], vec[right]);
  149.        
  150.         if (j == k)
  151.             return;
  152.         if (j > k)
  153.             HoareQuickSort(vec, left, j - 1, k);
  154.         if (j < k)
  155.             HoareQuickSort(vec, j + 1, right, k - j + left - 1);
  156.     }
  157. }
  158.  
  159. // Run-time complexity O(n)
  160. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  161.    
  162.     vector<Point> distances;
  163.     // O(n)
  164.     for (int i = 0; i < points_set.size(); ++i) {
  165.         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]);
  166.         Point np(points_set[i][0], points_set[i][1], dist);
  167.         distances.push_back(np);
  168.     }
  169.    
  170.     // O(n)
  171.     HoareQuickSort(distances, 0, distances.size() - 1, k);
  172.  
  173.     vector<vector<int>> ans(k, vector<int> (2));
  174.     // O(k)
  175.     for (int i = 0; i < k; ++i) {
  176.         vector<int> v = {distances[i].x, distances[i].y};
  177.         ans[i] = v;
  178.     }
  179.    
  180.     return ans;
  181. }
  182.  
  183. void PrintVector(const vector<vector<int>>& points_set) {
  184.  
  185.     for (int i = 0; i < points_set.size(); ++i) {
  186.         std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
  187.     }
  188. }
  189.  
  190. void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {
  191.    
  192.     int min_x = numeric_limits<int>::max();
  193.     int min_y = numeric_limits<int>::max();
  194.     int max_x = numeric_limits<int>::min();
  195.     int max_y = numeric_limits<int>::min();
  196.    
  197.     for (vector<int> point : points_set) {
  198.         if (point[0] < min_x)
  199.             min_x = point[0];
  200.         if (point[0] > max_x)
  201.             max_x = point[0];
  202.         if (point[1] > max_y)
  203.             max_y = point[1];
  204.         if (point[1] < min_y)
  205.             min_y = point[1];
  206.     }
  207.    
  208.     vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));
  209.    
  210.     for (int i = 0; i < grid.size(); ++i) {
  211.         for (int j = 0; j <grid[0].size(); ++j) {
  212.             for (vector<int> point : points_set) {
  213.                 if (point[0] == i && point[1] == j)
  214.                     grid[i][j] = 'x';
  215.             }
  216.             if (p[0] == i && p[1] == j)
  217.                 grid[i][j] = 'o';
  218.         }
  219.     }
  220.    
  221.     for (int i = 0; i < grid.size(); ++i) {
  222.         for (int j = 0; j < grid[0].size(); ++j) {
  223.             std::cout << grid[i][j] << " ";
  224.         }
  225.         std::cout << std::endl;
  226.     }
  227.    
  228. }
  229.  
  230. int main()
  231. {
  232.     srand(time(NULL));
  233.    
  234.     vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};
  235.    
  236.     vector<int> p{2, 4};
  237.  
  238.     int k = 5;
  239.    
  240.     vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);
  241.  
  242.     PrintGrid(points_set, p);
  243.  
  244.     PrintVector(kpoints_set);
  245.  
  246.     return 0;
  247. }
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