leetcode 1610 문제 풀이

https://leetcode.com/problems/maximum-number-of-visible-points/

Maximum Number of Visible Points - LeetCode

 

아이디어: view point 에서 angle 각도를 구해서 정렬 한뒤에 sort  -> 그위에 upper_bound 를 통해서 index 갯수를 전체 탐색 

nlog(n)

 

 
#define PI 3.1415926535
using namespace std;
double arr[200001];
 
class Solution {
 
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
 
        int felxAnswer = 0;        
        int cnt = 0;
 
        for (auto &pos : points) {
 
            if (pos == location) {
                felxAnswer++;
                continue;
            }
 
            double tmp = getDegree(pos[0] - location[0], pos[1] - location[1]);
            arr[cnt++] = tmp;
            arr[cnt++] = tmp + 360.0f;
        }
 
        sort(arr, arr + cnt);
        int range = 0;
        int ret_max = 0;
 
        for (int i = 0; i < cnt; i++) {
            range = upper_bound(arr + i, arr + cnt, arr[i] + angle) - (arr + i);
            ret_max = range > ret_max ? range : ret_max;
        }
 
        return ret_max + felxAnswer;
    }
 
    double getDegree(int x, int y) {
 
        double ret = atan2(y, x) * 180 / PI;
        return ret;
    }
};