• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

bbescos Feb 23rd, 2019 65 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. // Run-time complexity O(n)
139. vector<vector<int>> KNearestPoints(const vector<vector<int>>& points_set, const vector<int>& p, const int k) {
140.
141.     vector<Point> distances;
142.     // O(n)
143.     for (int i = 0; i < points_set.size(); ++i) {
144.         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]);
145.         Point np(points_set[i][0], points_set[i][1], dist);
146.         distances.push_back(np);
147.     }
148.
149.     // O(n)
150.     nth_element(distances.begin(), distances.begin() + k, distances.end(), [](Point i, Point j){return (i.distance < j.distance);});
151.
152.     vector<vector<int>> ans(k, vector<int> (2));
153.     // O(k)
154.     for (int i = 0; i < k; ++i) {
155.         vector<int> v = {distances[i].x, distances[i].y};
156.         ans[i] = v;
157.     }
158.
159.     return ans;
160. }
161.
162. void PrintVector(const vector<vector<int>>& points_set) {
163.
164.     for (int i = 0; i < points_set.size(); ++i) {
165.         std::cout << "(" << points_set[i][0] << ", " << points_set[i][1] << ")" << std::endl;
166.     }
167. }
168.
169. void PrintGrid(const vector<vector<int>>& points_set, const vector<int>& p) {
170.
171.     int min_x = numeric_limits<int>::max();
172.     int min_y = numeric_limits<int>::max();
173.     int max_x = numeric_limits<int>::min();
174.     int max_y = numeric_limits<int>::min();
175.
176.     for (vector<int> point : points_set) {
177.         if (point[0] < min_x)
178.             min_x = point[0];
179.         if (point[0] > max_x)
180.             max_x = point[0];
181.         if (point[1] > max_y)
182.             max_y = point[1];
183.         if (point[1] < min_y)
184.             min_y = point[1];
185.     }
186.
187.     vector<vector<char>> grid(max_x - min_x + 1, vector<char> (max_y - min_y + 1, '-'));
188.
189.     for (int i = 0; i < grid.size(); ++i) {
190.         for (int j = 0; j <grid[0].size(); ++j) {
191.             for (vector<int> point : points_set) {
192.                 if (point[0] == i && point[1] == j)
193.                     grid[i][j] = 'x';
194.             }
195.             if (p[0] == i && p[1] == j)
196.                 grid[i][j] = 'o';
197.         }
198.     }
199.
200.     for (int i = 0; i < grid.size(); ++i) {
201.         for (int j = 0; j < grid[0].size(); ++j) {
202.             std::cout << grid[i][j] << " ";
203.         }
204.         std::cout << std::endl;
205.     }
206.
207. }
208.
209. int main()
210. {
211.     vector<vector<int>> points_set{{0, 0}, {1, 5}, {3, 9}, {4, 0}, {2, 7}, {3, 2}, {4, 6}, {2, 3}};
212.
213.     vector<int> p{2, 4};
214.
215.     int k = 4;
216.
217.     vector<vector<int>> kpoints_set = KNearestPoints(points_set, p, k);
218.
219.     PrintGrid(points_set, p);
220.
221.     PrintVector(kpoints_set);
222.
223.     return 0;
224. }
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.
Not a member of Pastebin yet?