阿里巴巴国际站官网首页,郑州快速建站模板,重庆网站开发服务器,网站报价表文章目录1. 题目2. 解题1. 题目
给你一个点数组 points 和一个表示角度的整数 angle #xff0c;你的位置是 location #xff0c;其中 location [posx, posy] 且 points[i] [xi, yi] 都表示 X-Y 平面上的整数坐标。
最开始#xff0c;你面向东方进行观测。你 不能 进行…
文章目录1. 题目2. 解题1. 题目
给你一个点数组 points 和一个表示角度的整数 angle 你的位置是 location 其中 location [posx, posy] 且 points[i] [xi, yi] 都表示 X-Y 平面上的整数坐标。
最开始你面向东方进行观测。你 不能 进行移动改变位置但可以通过 自转 调整观测角度。 换句话说posx 和 posy 不能改变。你的视野范围的角度用 angle 表示 这决定了你观测任意方向时可以多宽。 设 d 为逆时针旋转的度数那么你的视野就是角度范围 [d - angle/2, d angle/2] 所指示的那片区域。
对于每个点如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中 那么你就可以看到它。
同一个坐标上可以有多个点。你所在的位置也可能存在一些点但不管你的怎么旋转总是可以看到这些点。同时点不会阻碍你看到其他点。
返回你能看到的点的最大数目。
示例 1
输入points [[2,1],[2,2],[3,3]], angle 90, location [1,1]
输出3
解释阴影区域代表你的视野。在你的视野中所有的点都清晰可见
尽管 [2,2] 和 [3,3]在同一条直线上你仍然可以看到 [3,3] 。示例 2
输入points [[2,1],[2,2],[3,4],[1,1]], angle 90, location [1,1]
输出4
解释在你的视野中所有的点都清晰可见包括你所在位置的那个点。示例 3
输入points [[0,1],[2,1]], angle 13, location [1,1]
输出1
解释如图所示你只能看到两点之一。提示
1 points.length 10^5
points[i].length 2
location.length 2
0 angle 360
0 posx, posy, xi, yi 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-number-of-visible-points 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
http://www.cplusplus.com/reference/cmath/atan2/?kwatan2
参考大佬解
class Solution {
public:int visiblePoints(vectorvectorint points, int angle, vectorint location) {int x, y, overlap 0;double PI 3.141592653, eps 1e-8;vectordouble ang;//与 x 轴的夹角for(int i 0 ; i points.size() ; i){x points[i][0]-location[0];y points[i][1]-location[1];if(x 0 y 0)//跟旋转轴重叠的{overlap;}else{ang.push_back(atan2(y, x)*180/PI);}}sort(ang.begin(), ang.end());int n ang.size();for(int i 0; i n; i)ang.push_back(ang[i]360);//再旋转添加一圈int j 0, ans 0;for(int i 0; i n; i)//以每个点为边界逆时针扫描{while(j ang.size() ang[j]-ang[i] angleeps){ans max(ans, j-i1);j;}}return ansoverlap;}
};1148 ms 128.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
