SHARE
TWEET

Untitled

bbescos Feb 24th, 2019 64 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() (const Point& p1, const Point& p2) {
  25.         return (p1.distance < p2.distance);
  26.     }
  27. } compare;
  28.  
  29. struct CompareMinHeap {
  30.     bool operator() (const Point& p1, const Point& p2) {
  31.         return (p1.distance > p2.distance);
  32.     }
  33. };
  34.  
  35. struct CompareMaxHeap {
  36.     bool operator() (const Point& p1, const 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. // Memory complexity O(n)
  45. /*
  46. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  47.    
  48.     // O(n)
  49.     vector<Point> distances;
  50.     distances.reserve(points_set.size());
  51.     for (int i = 0; i < points_set.size(); ++i) {
  52.         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]);
  53.         Point np(points_set[i][0], points_set[i][1], dist);
  54.         distances.emplace_back(np);
  55.     }
  56.    
  57.     // O(nlogn)
  58.     sort(distances.begin(), distances.end(), compare);
  59.    
  60.     // O(k)
  61.     vector<vector<int>> ans;
  62.     ans.reserve(k);
  63.     for (int i = 0; i < k; ++i)
  64.         ans.emplace_back(initializer_list<int>{distances[i].x, distances[i].y});
  65.    
  66.     return ans;
  67. }
  68. */
  69.  
  70. // Run-time complexity O(max(n, klogn)
  71. // Memory complexity O(n)
  72. /*
  73. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  74.    
  75.     // O(n)
  76.     vector<Point> distances;
  77.     distances.reserve(points_set.size());
  78.     for (int i = 0; i < points_set.size(); ++i) {
  79.         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]);
  80.         Point np(points_set[i][0], points_set[i][1], dist);
  81.         distances.emplace_back(np);
  82.     }
  83.    
  84.     // O(n)
  85.     priority_queue<Point, vector<Point>, CompareMinHeap> pq(distances.begin(), distances.end());
  86.    
  87.     // O(klogn)
  88.     vector<vector<int>> ans;
  89.     ans.reserve(k);
  90.     for (int i = 0; i < k; ++i) {
  91.         ans.emplace_back(initializer_list<int>{pq.top().x, pq.top().y});
  92.         pq.pop();
  93.     }
  94.    
  95.     return ans;
  96. }
  97. */
  98.  
  99. // Run-time complexity O(max(n + k + klogk + (n-k)logk)) = O(max(n + k + nlogk) = O(nlogk)
  100. // Memory complexity O(n)
  101. /*
  102. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  103.    
  104.     // O(n)
  105.     vector<Point> distances;
  106.     distances.reserve(points_set.size());
  107.     for (int i = 0; i < points_set.size(); ++i) {
  108.         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]);
  109.         Point np(points_set[i][0], points_set[i][1], dist);
  110.         distances.emplace_back(np);
  111.     }
  112.    
  113.     // O(k)
  114.     priority_queue<Point, vector<Point>, CompareMaxHeap> pq(distances.begin(), distances.begin() + k);
  115.    
  116.     // O((n-k)logk)
  117.     for (int i = k; i < points_set.size(); ++i) {
  118.         if (distances[i].distance < pq.top().distance) {
  119.             pq.pop();
  120.             pq.push(distances[i]);
  121.         }
  122.     }
  123.    
  124.     // O(klogk)
  125.     vector<vector<int>> ans;
  126.     ans.reserve(k);
  127.     for (int i = 0; i < k; ++i) {
  128.         ans.emplace_back(initializer_list<int>{pq.top().x, pq.top().y});
  129.         pq.pop();
  130.     }
  131.    
  132.     return ans;
  133. }
  134. */
  135.  
  136. void PrintVector(const vector<Point>& vec) {
  137.     for (Point p : vec) {
  138.         std::cout << p.distance << " ";
  139.     }
  140.     std::cout << std::endl;
  141. }
  142.  
  143. // Run-time complexity O(n)
  144. // Memory complexity O(n)
  145. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
  146.    
  147.     // O(n)
  148.     vector<Point> distances;
  149.     distances.reserve(points_set.size());
  150.     for (int i = 0; i < points_set.size(); ++i) {
  151.         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]);
  152.         Point np(points_set[i][0], points_set[i][1], dist);
  153.         distances.emplace_back(np);
  154.     }
  155.    
  156.     // O(n)
  157.     nth_element(distances.begin(), distances.begin() + k, distances.end(), [](const Point& i, const Point& j){return (i.distance < j.distance);});
  158.  
  159.     // O(k)
  160.     vector<vector<int>> ans;
  161.     ans.reserve(k);
  162.     for (int i = 0; i < k; ++i)
  163.         ans.emplace_back(initializer_list<int>{distances[i].x, distances[i].y});
  164.    
  165.     return ans;
  166. }
  167.  
  168.  
  169. void PrintVector(const vector<vector<int>>& points_set) {
  170.  
  171.     for (int i = 0; i < points_set.size(); ++i) {
  172.         std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
  173.     }
  174. }
  175.  
  176. void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {
  177.    
  178.     int min_x = numeric_limits<int>::max();
  179.     int min_y = numeric_limits<int>::max();
  180.     int max_x = numeric_limits<int>::min();
  181.     int max_y = numeric_limits<int>::min();
  182.    
  183.     for (vector<int> point : points_set) {
  184.         if (point[0] < min_x)
  185.             min_x = point[0];
  186.         if (point[0] > max_x)
  187.             max_x = point[0];
  188.         if (point[1] > max_y)
  189.             max_y = point[1];
  190.         if (point[1] < min_y)
  191.             min_y = point[1];
  192.     }
  193.    
  194.     vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));
  195.    
  196.     for (int i = 0; i < grid.size(); ++i) {
  197.         for (int j = 0; j <grid[0].size(); ++j) {
  198.             for (vector<int> point : points_set) {
  199.                 if (point[0] == i && point[1] == j)
  200.                     grid[i][j] = 'x';
  201.             }
  202.             if (p[0] == i && p[1] == j)
  203.                 grid[i][j] = 'o';
  204.         }
  205.     }
  206.    
  207.     for (int i = 0; i < grid.size(); ++i) {
  208.         for (int j = 0; j < grid[0].size(); ++j) {
  209.             std::cout << grid[i][j] << " ";
  210.         }
  211.         std::cout << std::endl;
  212.     }
  213.    
  214. }
  215.  
  216. int main()
  217. {
  218.     vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};
  219.    
  220.     vector<int> p{2, 4};
  221.  
  222.     int k = 4;
  223.    
  224.     vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);
  225.  
  226.     PrintGrid(points_set, p);
  227.  
  228.     PrintVector(kpoints_set);
  229.  
  230.     return 0;
  231. }
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