1610.maximum-number-of-visible-points 可见点的最大数目

问题描述

1610.可见点的最大数目

解题思路

利用atan2函数，即可将斜率转化为\(-\pi \sim \pi\)的角度;

扩充数组，令angle[n + i] = angle[i] + 360，使角度数组长度为2 * n，这样就能避免遗漏一四象限。

代码

class Solution {
  public:
    int visiblePoints(vector<vector<int>> &points, int angle, vector<int> &location) {
        vector<float> point_angle(points.size(), 0);
        for (int i = 0; i < points.size(); i++) {
            if (points[i][0] == location[0]) {
                if (points[i][1] > location[1])
                    point_angle[i] = 90;
                else if (points[i][1] == location[1])
                    point_angle[i] = 361; // 用来标记这是一个重叠的点
                else
                    point_angle[i] = -90;
            } else {
                point_angle[i] = atan2(points[i][1] - location[1], points[i][0] - location[0]) * 180 / M_PI;
            }
        }
        int cnt = 0;
        std::sort(point_angle.begin(), point_angle.end());
        for (int i = point_angle.size() - 1; i >= 0; i--) {
            if (point_angle[i] > 360) {
                point_angle.pop_back();
                cnt++;
            }
        }
        int ans = 0;
        vector<float> angle2(point_angle.size() * 2, 0);
        for (int i = 0; i < point_angle.size(); i++) {
            angle2[i] = point_angle[i];
            angle2[i + point_angle.size()] = point_angle[i] + 360;
        }

        int l = 0;

        for (int r = 0; r < angle2.size(); r++) {
            if (angle2[r] - angle2[l] > angle)
                while (l <= r && angle2[r] - angle2[l] > angle)
                    l++;
            else
                ans = max(ans, r - l + 1);
        }
        return ans + cnt;
    }
};