# 973 - K Closest Points to Origin

解法一 - Max Heap

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        // Store <point, dist> pair into maxHeap
        priority_queue< pair<vector<int>, float>, vector<pair<vector<int>, float>>, comp > maxHeap;

        for(auto& p: points) {
            float dist = sqrt( pow(p[0],2) + pow(p[1], 2) );
            maxHeap.push(make_pair(p, dist));

            if(maxHeap.size() > K) {
                maxHeap.pop();
            }
        }

        // Put all points in maxHeap into the result
        vector<vector<int>> res;
        for(int i = 0; i < K; i++) {
            res.push_back(maxHeap.top().first);
            maxHeap.pop();
        }

        return res;
    }

private:
    struct comp {
        bool operator() (const pair<vector<int>, float>& p1, 
                         const pair<vector<int>, float>& p2) {
            return p1.second < p2.second;
        }
    };
};