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

Top