在heap里就要排序，先按d排序，第二是x，第三是y？
1 维持一个大小为K的max-heap
2 然后后面每push一个进来，就把最长距离那个pop出去
3 所以push进heap的值是负的distance，因为到时候可以把最远距离的给pop出去
"""
Definition for a point.
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
"""
class Solution:
"""
@param points: a list of points
@param origin: a point
@param k: An integer
@return: the k closest points
"""
def kClosest(self, points, origin, k):
# write your code here
import heapq
heap = [(-self.distance(p,origin), p) for p in points[:k]]
heapq.heapify(heap)
ret = []
for p in points[k:]:
small_d, point = heapq.heappop(heap)
heapq.heappush(heap,(small_d,point))
d = self.distance(p, origin)
if d>-small_d:
continue
elif d<-small_d:
heapq.heappushpop(heap, (-d, p))
else:
if p.x<point.x:
heapq.heapreplace(heap, (-d, p))
elif p.y<point.y:
heapq.heapreplace(heap, (-d, p))
ret = [p for d, p in heap]
ret.sort(key=lambda item: (self.distance(item, origin), item.x, item.y))
return ret
def distance(self, point, origin):
return (point.x-origin.x)**2+(point.y-origin.y)**2
