// Merry April Fools! >:3
// Given a list of points, a central point, and an integer k, find the nearest k points from the central point.
// For example, given the list of points[(0, 0), (5, 4), (3, 1)], the central point(1, 2), and k = 2, return[(0, 0), (3, 1)].
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
double getDist(pair<int,int> p1, pair<int, int> p2)
{
double dist;
double x = p1.first - p2.first;
double y = p1.second - p2.second;
dist = pow(x, 2) + pow(y, 2);
return sqrt(dist);
}
struct less_than_key
{
inline bool operator() (const pair<double, int>& point1, const pair<double, int>& point2)
{
return (point1.first < point2.first);
}
};
vector<pair<int, int>> NearestPoints(int k, pair<int, int> center, vector<pair<int, int>> list)
{
vector<pair<int, int>> points = list;
vector<pair<double, int>> distances = vector<pair<double, int>>();
double maxDist = 0, dist = 0;
int h = 0, nearest = 0;
for (int i = 0; i < points.size(); ++i)
{
dist = getDist(points[i], center);
//sortedInsert(distances, pair<double, int>(dist, i));
// add new point (dist,index)
distances.push_back(pair<double, int>(dist, i));
sort(distances.begin(), distances.end(), less_than_key());
if (dist < maxDist)
{
nearest = i;
maxDist = dist;
}
}
vector<pair<int, int>> nearestPts = vector<pair<int, int>>();
pair<int, int> point;
// return k closest points
for (int i = 0; i < k; ++i)
{
// get the next nearest point's index
// and use that index to find the point we want to return
point = list[distances[i].second];
nearestPts.push_back(point);
}
return nearestPts;
}
int main()
{
int k = 3; // # of nearest points we want back
// generate list of points
vector<pair<int, int>> points = { pair<int, int>(0,0), pair<int, int>(5, 4), pair<int, int>(3, 1), pair<int, int>(2, 1) };
// center point for comparisons
pair<int, int> center = pair<int, int>(1,2);
vector<pair<int, int>> vec = NearestPoints(k, center, points);
cout << "Nearest points to (" << center.first << ", " << center.second << ") in order are:" << endl;
for (int i = 0; i < vec.size(); i++)
cout << "(" << vec[i].first << ", " << vec[i].second << ")" << endl;
return 0;
}
Kommentare