• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

bbescos Mar 3rd, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. #include <iostream>
3.
4. using namespace std;
5.
6. struct Point {
7.   float x;
8.   float y;
9.   Point(float x, float y) : x(x), y(y) {};
10. };
11.
12. struct DistPoint {
13.   float x;
14.   float y;
15.   float distance;
16.   DistPoint(float x, float y, float distance) : x(x), y(y), distance(distance) {};
17. };
18.
19. struct DistPoint {
20.   Point* p;
21.   float distance;
22.   DistPoint(Point* p, float distance) : p(p), distance(distance) {};
23. };
24.
25. // 1 4 2 9 3 2 N*MlogM (results are in order)
26.
27. // 2 1 2 3 9 4 N*M (results are not in order)
28.
29. // 1 2 2 9 3 4 N*k*logM - N*M*logk (results are in order)
30.
31.
32. vector<Point> KNearestNeighbors(const vector<Point>& map, const Point& query, const int k) {
33.
34.     vector<DistPoint> distances;
35.     distances.reserve(map.size());
36.     for (const Point& p : map) {
37.         float distance = (p.x - query.x)*(p.x - query.x) + (p.y - query.y)*(p.y - query.y);
38.         distances.emplace_back(p.x, p.y, distance); // distances.emplace_back(&p, distance);
39.     }
40.
41.     nth_element(distances.begin(), distances.begin() + k, distances.end(), [] (const DistPoint& p1, const DistPoint& p2) {
42.         return (p1.distance < p2.distance);
43.     });
44.
45.     vector<Point> solution;
46.     solution.reserve(k);
47.     for (int i = 0; i < k; ++i)
48.         solution.emplace_back(distances[i].x, distances[i].y); // solution.emplace_back(*(distances[i].p));
49.
50.     return solution;
51. }
52.
53. int main()
54. {
55.     vector<Point> map_points{{}}; M
56.
57.     Point query_point{}; N
58.
59.     int k = 4;
60.
61.     vector<Point> k_nearest_neighbors =  KNearestNeighbors(map_points, query_point, k);
62.
63.     return 0;
64. }
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?