Maximum Disc Coverage实现报错：无法找到findMaxDiscCoverage(java.util.List<Point>)方法求助

咱们一步步来拆解问题，先搞定编译报错，再修正逻辑上的坑：

一、直接导致编译错误的原因 #

1. 方法必须归属类 #

Java不允许在类外面定义方法，你写的createUnitCircle和findMaxDiscCoverage现在是游离在所有类之外的，编译器根本找不到它们。得把这俩方法放到一个类里，比如专门整个工具类DiscCoverageUtils。

2. 方法返回值不完整 #

如果输入的点列表只有1个或者0个点，外层循环根本不会执行，这时候方法没有任何return语句，编译肯定失败。得在方法末尾加个默认的return逻辑。

3. 错误的提前return #

你在findMaxDiscCoverage的内层循环里直接写了return maxDiscCoverage;，这会导致程序刚检查完第一对符合条件的点就直接返回，完全跳过了后面所有点对的遍历，逻辑直接崩了，同时也会引发编译路径问题。

二、逻辑错误修复 #

除了编译问题，代码里还有几个关键逻辑bug，会导致计算结果完全不对：

1. 圆包含点的判断错误 #

Circle类的containsPoints方法里，判断条件写的是centre.distanceTo(points.get(i)) <= 2，但咱们的圆半径是1啊！正确的判断应该是点到圆心的距离≤1（考虑浮点精度误差，可以写成<= 1.0 + 1e-6，避免浮点计算的小误差导致误判）。

2. 圆心计算的角度错误 #

Point类的angleTo方法实现完全错了，它现在算的是中点到原点的角度，而咱们需要的是垂直于两点连线的方向角度（因为单位圆的圆心在两点连线的垂直平分线上）。得基于两点的向量重新计算这个角度。

3. 浮点精度处理 #

当两点距离非常接近2时，dSquare = 1 - Math.pow(mqDistance, 2)可能因为浮点误差变成负数，导致Math.sqrt抛出异常，得先判断修正这个值。

4. 单点边界情况 #

当输入只有一个点时，最大覆盖数应该是1（以这个点为圆心的单位圆肯定包含它自己），你的代码没处理这种情况。

5. 遗漏另一个可能的单位圆 #

给定两个距离≤2的点，其实有两个不同的单位圆能同时包含它们（垂直平分线的两个方向），这两个圆的覆盖点数可能不一样，得都算一遍。

三、修复后的完整代码 #

class Point {
    private final double x;
    private final double y;
    static final double EPS = 1e-6; // 浮点误差容忍值

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    Point midPoint(Point q) {
        return new Point((this.x + q.x) / 2, (this.y + q.y) / 2);
    }

    double distanceTo(Point q) {
        return Math.sqrt(Math.pow(this.x - q.x, 2) + Math.pow(this.y - q.y, 2));
    }

    // 计算垂直于当前点到目标点连线的方向角度
    double perpendicularAngleTo(Point q) {
        double dx = q.x - this.x;
        double dy = q.y - this.y;
        // 垂直方向的向量是(-dy, dx)，对应角度为原向量角度+90度
        return Math.atan2(dy, dx) + Math.PI / 2;
    }

    Point moveTo(double theta, double d) {
        return new Point(this.x + d * Math.cos(theta), this.y + d * Math.sin(theta));
    }

    @Override
    public String toString() {
        return "point (" + String.format("%.3f", this.x) + ", " + String.format("%.3f", this.y) + ")";
    }
}

class Circle {
    private final Point centre;
    private final double radius;

    Circle(Point centre, double radius) {
        this.centre = centre;
        this.radius = radius;
    }

    public int containsPoints(List<Point> points) {
        int numOfPoints = 0;
        for (Point p : points) {
            // 考虑浮点误差，判断点到圆心距离是否≤半径
            if (centre.distanceTo(p) <= radius + Point.EPS) {
                numOfPoints++;
            }
        }
        return numOfPoints;
    }

    @Override
    public String toString() {
        return "circle of radius " + this.radius + " centered at " + this.centre;
    }
}

import java.util.List;

public class DiscCoverageUtils {

    public static Circle createUnitCircle(Point p, Point q, boolean isPositiveDirection) {
        double pqDistance = p.distanceTo(q);
        Point midPoint = p.midPoint(q);
        double halfDistance = pqDistance / 2;

        // 处理浮点精度，避免根号下出现负数
        double dSquare = 1 - Math.pow(halfDistance, 2);
        if (dSquare < 0) {
            dSquare = 0;
        }
        double d = Math.sqrt(dSquare);

        // 获取垂直方向角度，支持两个方向
        double theta = p.perpendicularAngleTo(q);
        if (!isPositiveDirection) {
            theta -= Math.PI;
        }
        Point centre = midPoint.moveTo(theta, d);
        return new Circle(centre, 1);
    }

    public static int findMaxDiscCoverage(List<Point> points) {
        // 处理单点或空列表的边界情况
        if (points.size() <= 1) {
            return points.size();
        }

        int maxDiscCoverage = 1; // 至少能包含一个点
        int numOfPoints = points.size();

        for (int i = 0; i < numOfPoints; i++) {
            for (int j = i + 1; j < numOfPoints; j++) {
                Point point1 = points.get(i);
                Point point2 = points.get(j);

                // 两点距离超过2，无法构造同时包含它们的单位圆
                if (point1.distanceTo(point2) > 2 + Point.EPS) {
                    continue;
                }

                // 构造两个方向的单位圆，分别计算覆盖点数
                Circle c1 = createUnitCircle(point1, point2, true);
                int count1 = c1.containsPoints(points);

                Circle c2 = createUnitCircle(point1, point2, false);
                int count2 = c2.containsPoints(points);

                // 更新最大覆盖数
                maxDiscCoverage = Math.max(maxDiscCoverage, Math.max(count1, count2));
            }
        }

        return maxDiscCoverage;
    }
}

四、使用示例 #

现在你可以这样调用方法：

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Point> points = new ArrayList<>();
        points.add(new Point(0, 0));
        points.add(new Point(1, 0));
        points.add(new Point(0, 1));

        int maxCoverage = DiscCoverageUtils.findMaxDiscCoverage(points);
        System.out.println("最大覆盖点数：" + maxCoverage); // 输出3
    }
}

内容的提问来源于stack exchange，提问作者nicetomeetyou98