讨论/题目交流/🏆 第 189 场力扣周赛/
🏆 第 189 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 在既定时间做作业的学生人数
4 分 - 重新排列句子中的单词
5 分 - 收藏清单
7 分 - 圆形靶内的最大飞镖数量

展开讨论
力扣 (LeetCode)发起于 2020-05-17

圆形靶内的最大飞镖数量

此题其实算是高中数学向量部分以及初中数学勾股定理的应用。
考虑一个半径恒定为r的圆,其覆盖若干(≥2)点,现移动这个圆,则必然存在这种情况:这个圆覆盖的点数不变或增加,且其边界至少通过这些点中的2个。
因此,我们只要求通过两点且半径为r的圆心即可。
image.png
一个比较简单的方法是:求出中点,求出法向(和线段垂直),求出距离(用勾股定理)。有了这三项,即可求出圆心的位置。
之后,只要遍历所有的两点,求出圆心,再计算出落在其中的点的数量即可。

class Solution {
    //获得给定两点坐标和半径,获得圆心。
    public double[] getCenter(int x0,int y0,int x1,int y1,int r){
        int dx=x1-x0,dy=y1-y0;
        double dist=Math.sqrt(dx*dx+dy*dy);
        if(dist>2*r)
            return new double[0]; //不可能有圆心
        double midx=(x0+x1)/2.0,midy=(y0+y1)/2.0;
        if(dist==2*r)
            return new double[]{midx,midy}; //圆心只有1种可能
        double offset=Math.sqrt(r*r-dist*dist/4);
        double offx=-dy/dist,offy=dx/dist;
        return new double[]{midx+offx*offset,midy+offy*offset,midx-offx*offset,midy-offy*offset}; //圆心有2种可能
    }

    public int numPoints(int[][] points, int r) {
        int max=1;
        int length=points.length;
        for(int i=0;i<length;i++){
            for(int j=i+1;j<length;j++){
                double[]center=getCenter(points[i][0],points[i][1],points[j][0],points[j][1],r); //获得所有可能的圆心
                if(center.length<=0)continue;
                int count=0;
                for(int t=0;t<length;t++){
                    double dx=points[t][0]-center[0];
                    double dy=points[t][1]-center[1];
                    if(dx*dx+dy*dy<r*r+0.000001) //计算距离时由于double类型大小比较存在精度问题,所以此处略微扩大r
                        count++;
                }
                if(count>max)
                    max=count;
                if(center.length>=4){ //2个圆心需要分别计算
                    count=0;
                    for(int t=0;t<length;t++){
                        double dx=points[t][0]-center[2];
                        double dy=points[t][1]-center[3];
                        if(dx*dx+dy*dy<r*r+0.000001)
                            count++;
                    }
                    if(count>max)
                        max=count;
                }
            }
        }
        return max;
    }
}
6
展开全部 17 讨论