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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top