• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

bbescos Feb 23rd, 2019 70 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.

Top