1610. 可见点的最大数目
给你一个点数组 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 = [[1,0],[2,1]], angle = 13, location = [1,1] 输出：1 解释：如图所示，你只能看到两点之一。
提示：
1 <= points.length <= 105points[i].length == 2location.length == 20 <= angle < 3600 <= posx, posy, xi, yi <= 100
1 import java.util.ArrayList;
2 import java.util.Arrays;
3 import java.util.Collections;
4 import java.util.List;
5
6 public class VisiblePoints {
7 public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
8 // delta x>0 delta y>0 为0~90°
9 // delta x<0 delta y>0 为90~180°
10 // delta x<0 delta y<0 为-90~-180°
11 // delta x>0 delta y<0 为-90~0°
12 // 特殊情况还有0，90,180，-180
13 ArrayList<Double> angles = new ArrayList<>();
14 int x=location.get(0),y=location.get(1);
15 int ansf=0;
16 for (int i = 0; i < points.size(); i++) {
17 int tx=points.get(i).get(0),ty=points.get(i).get(1);
18 if (tx==x||ty==y){
19 //特殊情况
20 if (tx==x&&ty>y)angles.add(90.0);
21 else if (tx==x&&ty<y) angles.add(-90.0);
22 else if (ty==y&&tx>x) angles.add(0.0);
23 else if (ty==y&&tx<x) angles.add(180.0);
24 else ansf++;//重合的点
25 }else {
26 double tan = (ty - y) * 1.0 / (tx - x);
27 if (tx - x > 0 && ty - y > 0) angles.add(Math.atan(tan) * 180 / Math.PI);
28 else if (tx - x > 0 && ty - y < 0) angles.add(Math.atan(tan) * 180 / Math.PI);
29 else if (tx - x < 0 && ty - y > 0) angles.add(180 - Math.atan(-tan) * 180 / Math.PI);
30 else angles.add(Math.atan(tan) * 180 / Math.PI - 180);
31 }
32 }
33 Collections.sort(angles);
34 System.out.println(angles);
35 System.out.println(ansf);
36 int MAX=0,tp;
37 for (int i = 0; i < angles.size(); i++) {
38 //优化为二分查找
39 //第一种情况，从该点出发，到列表末尾依然可以包括，则需要考虑列表前
40 if (angles.get(angles.size()-1)-angles.get(i)-angle<0.00001){
41 tp=binSearch(angles,-360+angles.get(i)+angle);
42 MAX=Math.max(MAX,angles.size()-i+tp+1);
43 }else {
44 tp=binSearch(angles,angles.get(i)+angle);
45 MAX=Math.max(MAX,tp-i+1);
46 }
47 //第二种情况，从该点出发，最大索引在末尾前，直接二分查找。
48
49 }
50 return MAX+ansf;
51 }
52 public int binSearch(List<Double> list,double num){
53 int l=0,r=list.size();
54 while (l<r){
55 int mid=(l+r)/2;
56 if (Math.abs(list.get(mid)-num)<0.0001){
57 l=mid+1;
58 }else if (list.get(mid)>num){
59 r=mid;
60 }else{
61 l=mid+1;
62 }
63 }
64 return l-1;
65 }
66 public static void main(String[] args) {
67 List<List<Integer>> arrayLists = new ArrayList<>();
68 ArrayList<Integer> i1 = new ArrayList<>();
69 i1.add(1);
70 i1.add(1);
71 arrayLists.add(i1);
72 ArrayList<Integer> i2 = new ArrayList<>();
73 i2.add(2);
74 i2.add(2);
75 arrayLists.add(i2);
76 ArrayList<Integer> i3 = new ArrayList<>();
77 i3.add(3);
78 i3.add(3);
79 arrayLists.add(i3);
80 ArrayList<Integer> i6 = new ArrayList<>();
81 i6.add(4);
82 i6.add(4);
83 arrayLists.add(i6);
84 ArrayList<Integer> i7 = new ArrayList<>();
85 i7.add(1);
86 i7.add(2);
87 arrayLists.add(i7);
88 ArrayList<Integer> i8 = new ArrayList<>();
89 i8.add(2);
90 i8.add(1);
91 arrayLists.add(i8);
92 ArrayList<Integer> i4 = new ArrayList<>();
93 i4.add(1);
94 i4.add(1);
95 System.out.println(new VisiblePoints().visiblePoints(arrayLists,0,i4));
96 }
97
98 }
可以利用arctan2x加反转来简化二分查找或者滑动窗口的时间复杂度。