# 973. K Closest Points to Origin
import heapq
from math import sqrt
"""
given an array of 'points' where 'points[i] = [x_i, y_i]' represents a point
on the x-y plane and an integer 'k', return the 'k' closest points to the
origin '(0, 0)'. the distance between two points on the x-y plane is the
euclidean distance (ie. 'sqrt((x1 - x2)^2 + (y1 - y2)^2))'. you may return
the answer in any order. the answer is guaranteed to be unique (except for
the order that it is in).
"""
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.dist = sqrt(x**2 + y**2)
def __lt__(self, other):
return self.dist < other.dist
class Solution(object):
def kClosest(self, points, k):
"""
:type points: List[List[int]]
:type k: int
:rtype: List[List[int]]
"""
min_heap, ans = [], []
for x, y in points:
node = Node(x, y)
heapq.heappush(min_heap, node)
for _ in range(k):
top = heapq.heappop(min_heap)
ans.append([top.x, top.y])
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.kClosest(points=[[1, 3], [-2, 2]], k=1))
print(obj.kClosest(points=[[3, 3], [5, -1], [-2, 4]], k=2))
