LintCode K个最近的点

问题

给定一些 points 和一个 origin，从 points 中找到 k 个离 origin 最近的点。按照距离由小到大返回。如果两个点有相同距离，则按照x值来排序；若x值也相同，就再按照y值排序

  """
  @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):
    # if list < knum just return
    if len(points)<=k: return points
    # function to calculate distance between origin and certain point
    def distanceBetween(pin):
      return math.sqrt(math.pow(pin.x-origin.x,2)+math.pow(pin.y-origin.y,2))
    allDis=[]
    for pin in points:
      dis=distanceBetween(pin)
      allDis.append({
        "x":pin.x,
        "y":pin.y,
        "dis":dis
      })
    # sort values according dis,x,y 
    sortValues=sorted(allDis, key=lambda p:(p["dis"],p["x"],p["y"]))
    # reform points
    result=[[dic["x"],dic["y"]] for dic in sortValues]
    print(result)