AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

最小元覆盖

作者: 作者的头像   不知名的fE ,  2025-05-08 14:57:49 · 河北 ,  所有人可见 ,  阅读 4


0


屏幕截图 2025-05-08 145401.png

import java.util.*;

public class Main {
    static final int N = 100010;
    static final double eps = 1e-8;
    static Point[] p = new Point[N];
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            double x = sc.nextDouble(), y = sc.nextDouble();
            p[i] = new Point(x, y);
        }

        Random random = new Random();
        for (int i = 1; i <= n; i++) {
            int j = random.nextInt(n + 1);
            if (j == 0) {
                i --;
                continue;
            }
            Point temp = p[j];
            p[j] = p[i];
            p[i] = temp;
        }

        Point o = p[1];
        double r = 0;
        for (int i = 1; i <= n; i++) {
            if (sgn(getDis(o, p[i]) - r) > 0) {
                o = p[i];
                r = 0;
                for (int j = 1; j < i; j++) {
                    if (sgn(getDis(o, p[j]) - r) > 0) {
                        o = new Point((p[i].x + p[j].x) / 2, (p[i].y + p[j].y) / 2);
                        r = getDis(o, p[j]);
                        for (int k = 1; k < j; k++) {
                            if (sgn(getDis(o, p[k]) - r) > 0) {
                                o = getCirCenter(p[i], p[j], p[k]);
                                r = getDis(o, p[k]);
                            }
                        }
                    }
                }
            }
        }

        System.out.printf("%.6f %.6f\n", o.x, o.y);
        System.out.printf("%.6f\n", r);
    }

    static Point getCirCenter(Point a, Point b, Point c) {
        double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
        double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;

        double d = a1 * b2 - a2 * b1;
        double x = a.x + (c1 * b2 - c2 * b1) / d;
        double y = a.y + (a1 * c2 - a2 * c1) / d;
        return new Point(x, y);
    }

    static double getDis(Point a, Point b) {
        double t1 = a.x - b.x, t2 = a.y - b.y;
        return Math.sqrt(t1 * t1 + t2 * t2);
    }

    static int sgn(double x) {
        if (Math.abs(x) < eps) return 0;
        else return x > 0 ? 1 : -1;
    }
}

class Point {
    double x, y;

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

圆心

08E35F907698B45B1630502BAE7D1F45.png

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息