• API
• FAQ
• Tools
• Archive
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.

Top