(工作预备)lc每日一题
思路:
类似极角排序加双指针,不知道那个夹角怎么求,结果看题解可以atan2求。
atan2大概是这么个分布,然后双指针即可,记得把数组扩增两倍再加个2pi,每次更新最大值即可,还有个细节就是和源点在同一点直接加就行。
const double PI=acos(-1);
class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
vector<double>v;
int res=0;
for(auto vv:points)
{
if(vv==location &&vv==location)
{
res++;
continue;
}
v.emplace_back(atan2(location-vv,location-vv));
}
sort(v.begin(),v.end());
int n=v.size();
for(int i=0;i<n;i++){
v.emplace_back(v+2*PI);
}
int ans=0;
double ag=angle*1.0/180*PI;
n=v.size(); int j=0;
for(int i=0;i<n;i++){
while(j<n && v-v<=ag)j++;
ans=max(ans,j-i);
}
return ans+res;
}
};
https://blog.51cto.com/u_15287527/4848503
页:
[1]