圆形靶内的最大飞镖数量Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] = [xi, yi] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。

Bob 知道墙上所有 n 支飞镖的位置。他想要往墙上放置一个半径为 r 的圆形靶。使 Alice 掷出的飞镖尽可能多地落在靶上。

给你整数 r ，请返回能够落在任意半径为 r 的圆形靶内或靶上的最大飞镖数。

示例 1 ：

输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。

示例 2 ：

输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。

提示：

1 <= darts.length <= 100
darts[i].length == 2
-104 <= xi, yi <= 104
darts 中的元素互不相同
1 <= r <= 5000

# 思路

已知两点坐标和半径求圆心坐标，然后遍历points，所有到圆心距离小于半径的都满足条件。

# 解法

class Solution {
    double diff = 1e-8;
    public int numPoints(int[][] points, int r) {
        int res = 1;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                double x1 = points[i][0];
                double y1 = points[i][1];
                double x2 = points[j][0];
                double y2 = points[j][1];
                double q = Math.sqrt(Math.pow((x2 - x1), 2) + Math.pow((y2 - y1), 2));
                double y3 = (y1 + y2) / 2;
                double x3 = (x1 + x2) / 2;
                double a = Math.sqrt(Math.pow(r, 2) - Math.pow((q / 2), 2));
                double basex = a * (y1 - y2) / q;
                double basey = a * (x2 - x1) / q;
                double centerx1 = x3 + basex;
                double centery1 = y3 + basey;
                double centerx2 = x3 - basex;
                double centery2 = y3 - basey;
                res = Math.max(res, count(centerx1, centery1, r, points));
                if (centerx1 != centerx2 || centery1 != centery2)
                    res = Math.max(res, count(centerx2, centery2, r, points));
            }
        }
        return res;
    }
    int count(double x, double y, double r, int[][] points) {
        int cnt = 0;
        for (int[] point : points) {
            int a = point[0];
            int b = point[1];
            if ((a - x) * (a - x) + (b - y) * (b - y) <= r * r + diff) cnt++;
        }
        return cnt;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 总结

分析出几种情况，然后分别对各个情况实现

#Java