java 解法, 执行用时: 140 ms, 内存消耗: 43.3 MB, 提交时间: 2023-09-18 14:58:28

class Solution {
    public double get_distance(double x1,double x2,double y1,double y2){
        double s=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
        return s;
    }
    public int numPoints(int[][] points, int r) {
        if(points.length<2)return points.length;
        int res=1;
        double d,x,y,center_x,center_y,h,x1,x2,y1,y2;
        for(int i=0;i<points.length;i++){
            for(int j=0;j<points.length;j++){
                if(i==j)continue;
                x1=points[i][0];
                y1=points[i][1];
                x2=points[j][0];
                y2=points[j][1];
                d=Math.sqrt(get_distance(x1,x2,y1,y2));
                if(d>2*r)continue;
                else{
                    x=(x1+x2)/2;
                    y=(y1+y2)/2;
                    if(x1==x2){
                       center_x=x;
                       center_y=y;
                    }
                    else{
                        h=Math.sqrt(r*r-(d/2)*(d/2));
                        center_x=h*(y2-y1)/d+x;
                        center_y=-h*(x2-x1)/d+y;
                    }   
                }
                System.out.println(center_x+" "+center_y);
                int count=0;
                for(int k=0;k<points.length;k++){
                    if(get_distance(points[k][0],center_x,points[k][1],center_y)-r*r<=0.00001){
                        count++;    
                    }   
                }
                res=Math.max(count,res);
            }
        }
        return res;
    }
}

python3 解法, 执行用时: 184 ms, 内存消耗: 17.4 MB, 提交时间: 2023-09-18 14:53:46

class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        def helper(i, r, n):
            angles = []
            for j in range(n):
                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:
                    C = math.acos(math.sqrt(l2) / (2 * r))
                    T = math.atan2(vec[i][j][1], vec[i][j][0])
                    _in = T - C
                    _out = T + C
                    angles.append([_in, True])
                    angles.append([_out, False])
            # 这里排序是重点, 考虑边界条件
            # 比如有 [0, False], [0, True]
            # 要让[0, True] 排到 [0, False]前面
            angles.sort(key=lambda x: [x[0], - x[1]])
            cnt = res = 1
            for item in angles:
                if item[1]:
                    cnt += 1
                else:
                    cnt -= 1
                if cnt > res:
                    res = cnt
            return res

        n = len(points)
        if n == 1:
            return 1
        # vec[i][j] = [Jx - Ix, J_y - Iy]
        # vec 存入两点之间的方向向量
        vec = [[[0, 0] for _ in range(n)] for __ in range(n)]
        for i in range(n - 1):
            for j in range(i + 1, n):
                JxIx = points[j][0] - points[i][0]
                JyIy = points[j][1] - points[i][1]
                vec[i][j] = [JxIx, JyIy]
                vec[j][i] = [-JxIx, -JyIy]
        ans = 0
        for i in range(n):
            ans = max(ans, helper(i, r, n))

        return ans

cpp 解法, 执行用时: 24 ms, 内存消耗: 14.8 MB, 提交时间: 2023-09-18 14:53:17

// Angular Sweep算法
const double PI = acos(-1);

class Solution {
public:
    int numPoints(vector<vector<int>>& points, int r) {
        if (points.empty()) return 0;
        int n = points.size();
        int ans = 1;
        // 遍历每一个点
        for (int i = 0; i < n; ++i) {
            vector<pair<double, double>> items;
            // 将能被覆盖的点的入角和出角加入 items
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                // 计算向量
                double xjxi = points[j][0] - points[i][0];
                double yjyi = points[j][1] - points[i][1];
                double dij = sqrt(xjxi * xjxi + yjyi * yjyi);
                if (dij > 2 * r + 1e-6) continue;
                // 计算角度
                double a = atan(yjyi / xjxi);
                if (xjxi < 0) a = (yjyi > 0) ? a + PI : a - PI; // 扩展到[-pi, pi]区域
                double b = acos(dij / (r * 2));
                items.push_back({a - b, -1});  
                items.push_back({a + b, 1});
            }
            sort(items.begin(), items.end());
            int cnt = 1;
            for (auto &p: items) {
                cnt -= p.second;
                if (cnt > ans) ans = cnt;
            }
        }
        return ans;
    }
};

cpp 解法, 执行用时: 24 ms, 内存消耗: 8.1 MB, 提交时间: 2023-09-18 14:51:29

struct point{
    double x,y;
    point(double i,double j):x(i),y(j){}
};

//算两点距离
double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

//计算圆心
point f(point& a,point& b,int r){
    //算中点
    point mid((a.x+b.x)/2.0,(a.y+b.y)/2.0);
    //AB距离的一半
    double d=dist(a.x,a.y,mid.x,mid.y);
    //计算h
    double h=sqrt(r*r-d*d);
    //计算垂线
    point ba(b.x-a.x,b.y-a.y);
    point hd(-ba.y,ba.x);
    double len=sqrt(hd.x*hd.x+hd.y*hd.y);
    hd.x/=len,hd.y/=len;
    hd.x*=h,hd.y*=h;
    return point(hd.x+mid.x,hd.y+mid.y);
}

class Solution {
public:
    int numPoints(vector<vector<int>>& points, int r) {
        int n=points.size();
        //！！！！！r >= 1 所以初始化点必然是1，这样后续的i = j的计算可以省略
        int ans=1;
        for(int i=0;i<n;i++){
           //！！！！！从j + 1开始即可，对称的计算
            for(int j=i + 1;j<n;j++){
               
                    double d=dist(points[i][0],points[i][1],points[j][0],points[j][1]);
                    if(d/2>r) continue;

                    point a(points[i][0],points[i][1]),b(points[j][0],points[j][1]);
                    point res=f(a,b,r);
                    int cnt=0;
                    for(int k=0;k<n;k++){
                        double tmp=dist(res.x,res.y,points[k][0],points[k][1]);
                        if(tmp < r || fabs(tmp - r) < 1e-5) cnt++;
                    }
                    ans=max(cnt,ans);
                
            }
        }
        return ans;
    }
};