daily pastebin goal
86%
SHARE
TWEET

Untitled

bbescos Feb 23rd, 2019 60 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 = left - 1;
  144.         for (int i = left; i <= right - 1; ++i) {
  145.             if (vec[i].distance < pivot.distance)
  146.                 swap(vec[i], vec[++j]);
  147.         }
  148.         swap(vec[++j], vec[right]);
  149.        
  150.         PrintVector(vec);
  151.        
  152.         if (j - left == k - 1)
  153.             return;
  154.         if (j - left > k - 1)
  155.             HoareQuickSort(vec, left, j - 1, k);
  156.  
  157.         HoareQuickSort(vec, j + 1, right, k - j + left - 1);
  158.     }
  159.    
  160.     return;
  161. }*/
  162.  
  163. // Run-time complexity O(n)
  164. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  165.    
  166.     vector<Point> distances;
  167.     // O(n)
  168.     for (int i = 0; i < points_set.size(); ++i) {
  169.         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]);
  170.         Point np(points_set[i][0], points_set[i][1], dist);
  171.         distances.push_back(np);
  172.     }
  173.    
  174.     // O(n)
  175.     nth_element(distances.begin(), distances.begin() + k, distances.end(), [](Point i, Point j){return (i.distance < j.distance);});
  176.  
  177.     vector<vector<int>> ans(k, vector<int> (2));
  178.     // O(k)
  179.     for (int i = 0; i < k; ++i) {
  180.         vector<int> v = {distances[i].x, distances[i].y};
  181.         ans[i] = v;
  182.     }
  183.    
  184.     return ans;
  185. }
  186.  
  187. void PrintVector(const vector<vector<int>>& points_set) {
  188.  
  189.     for (int i = 0; i < points_set.size(); ++i) {
  190.         std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
  191.     }
  192. }
  193.  
  194. void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {
  195.    
  196.     int min_x = numeric_limits<int>::max();
  197.     int min_y = numeric_limits<int>::max();
  198.     int max_x = numeric_limits<int>::min();
  199.     int max_y = numeric_limits<int>::min();
  200.    
  201.     for (vector<int> point : points_set) {
  202.         if (point[0] < min_x)
  203.             min_x = point[0];
  204.         if (point[0] > max_x)
  205.             max_x = point[0];
  206.         if (point[1] > max_y)
  207.             max_y = point[1];
  208.         if (point[1] < min_y)
  209.             min_y = point[1];
  210.     }
  211.    
  212.     vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));
  213.    
  214.     for (int i = 0; i < grid.size(); ++i) {
  215.         for (int j = 0; j <grid[0].size(); ++j) {
  216.             for (vector<int> point : points_set) {
  217.                 if (point[0] == i && point[1] == j)
  218.                     grid[i][j] = 'x';
  219.             }
  220.             if (p[0] == i && p[1] == j)
  221.                 grid[i][j] = 'o';
  222.         }
  223.     }
  224.    
  225.     for (int i = 0; i < grid.size(); ++i) {
  226.         for (int j = 0; j < grid[0].size(); ++j) {
  227.             std::cout << grid[i][j] << " ";
  228.         }
  229.         std::cout << std::endl;
  230.     }
  231.    
  232. }
  233.  
  234. int main()
  235. {
  236.     vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};
  237.    
  238.     vector<int> p{2, 4};
  239.  
  240.     int k = 4;
  241.    
  242.     vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);
  243.  
  244.     PrintGrid(points_set, p);
  245.  
  246.     PrintVector(kpoints_set);
  247.  
  248.     return 0;
  249. }
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