正方形中的最多点数

二分枚举所有的半边长，然后进行验证来找到合法正方形能包含的最多点数

class Solution {
public:
    int check(long long i, vector<vector<int>>& points, string s) {
        unordered_set<char> labels;
        int cnt = 0;
        for (int idx = 0; idx < points.size(); idx++) {
            long long x = points[idx][0];
            long long y = points[idx][1];
            // 判断点是否在正方形内
            if (abs(x) <= i && abs(y) <= i) {
                char c = s[idx];
                if (labels.count(c)) {
                    // 存在重复标签，该正方形不合法
                    return -1;
                }
                labels.insert(c);
                cnt++;
            }
        }
        // 无重复标签，返回点数
        return cnt;
    }

    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        vector<long long> candidates;
        for (auto& p : points) {
            candidates.push_back(abs(p[0]));
            candidates.push_back(abs(p[1]));
        }
        candidates.push_back(0);
        // 去重
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

        int max_cnt = 0;
        // 二分所有可能的半边长
        int left = 0, right = candidates.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            long long i = candidates[mid];
            int cnt = check(i, points, s);
            if (cnt != -1) {
                // 合法
                max_cnt = cnt;
                left = mid + 1;
            } else {
                // 不合法
                right = mid - 1;
            }
        }
        return max_cnt;
    }
};

时间复杂度： O(nlogn)