1 条题解

  • 0
    @ 2026-5-5 1:01:47

    二分答案,并假设有一个点在圆周上,否则可以调整到更优。

    枚举这个点,想象这个圆绕着这个点转一周的过程(也就是,扫描圆心对这个点的角度)。意在转的过程中,半径会实时发生变化。

    对于每个其他的点,存在一个角度区间使得其在圆中。可以二分求出这个区间。

    求出区间后,对角度扫描线即可。

    直接做的时间复杂度是 O(n2lognlog1ϵ)O(n^2\log n\log \frac{1}{\epsilon}),可以通过随机打乱 + 只对改变答案的点二分的 trick 优化到 O(n2logn+nlog2nlog1ϵ)O(n^2\log n + n\log^2 n \log \frac{1}{\epsilon})

    • 1

    信息

    ID
    7348
    时间
    5000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者