/**
* @param points a list of points
* @param origin a point
* @param k an integer
* @return the k closest points
*/
public Point[] kClosest(Point[] points, Point origin, int k) {
final Point global_origin = origin;
PriorityQueue<Point> priorityqueue = new PriorityQueue<Point>(k, new Comparator<Point>(){
@Override
public int compare(Point a, Point b){
int diff = getDistance(b, global_origin) - getDistance(a, global_origin);
if(diff == 0){
diff = b.x - a.x;
}
if(diff == 0){
diff = b.y - a.y;
}
return diff;
}
});
for(int i = 0; i < points.length; i++){
priorityqueue.offer(points[i]);
if(priorityqueue.size() > k){
priorityqueue.poll();
}
}
k = priorityqueue.size();
Point[] res = new Point[k];
while(!priorityqueue.isEmpty()){
res[--k] = priorityqueue.poll();
}
return res;
}
private int getDistance(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

### Like this:

Like Loading...

*Related*