ICPC 2024 江西省赛 Neuvillette Circling

题目大意

CF gym 105231 I - Neuvillette Circling | rating 2100 | 2024 (ICPC) 江西省赛 武大 WHU 命题组 | $n \le 100$ ，时限 2 秒

给 $N$ 个宝藏在平面上 $(x_i, y_i)$ ，任意两个宝藏之间有一条线段（路径），每条路径上有一个丘丘人——它可能出现在线段上的任意一点（位置对抗性）。Neuvillette 画一个圆（圆心任选、半径要最小），圆上或圆内的丘丘人被秒。

要求：无论这些丘丘人具体站在各自线段的哪个位置，他都能至少干掉 $m$ 个。对 $m = 1, 2, \dots, \binom{n}{2}$ 分别输出最小半径。

数据范围

• $2 \le n \le 100$

• $-10^3 \le x_i, y_i \le 10^3$ ，坐标全是整数

• 保证无两点重合 / 无三点共线

• 答案精度 $10^{-6}$

样例 ( $n = 5$ )

输入：

5
-6 -9
2 4
9 2
1 -1
-4 -5

输出（10 行）：

2.23606798
4.28602124
4.28602124
7.38241153
7.38241153
7.38241153
9.30053762
9.30053762
9.30053762
9.30053762

思路讲解

一句话

对抗性建模 $\to$ 「包住整段」等价于「包住两端点」（圆盘是凸集） $\to$ 圆里有 $k$ 个原始点就保证 $\binom{k}{2}$ 条边的丘丘人都被秒 $\to$ 题目变成 对每个 $k$ 求最小 $k$ 点覆盖圆。MEC 定理给出候选圆只有 $O(n^3)$ 个：两点直径 + 三点外接。总复杂度 $O(n^4)$ ， $n = 100$ 下宽松到不用卡常。

Step 1：对抗性建模——把「覆盖一条边」翻译成「包住两个点」

题目说丘丘人可能出现在线段任意一点，又要求无论它在哪都得能杀掉。这是经典对抗设定：玩家先确定圆，丘丘人才挑位置。

「保证这条边上的丘丘人被秒」 $\Longleftrightarrow$ 「整条线段在圆盘内」

否则对手把丘丘人放在圆外那一点。

再用「圆盘是凸集」收一刀——圆盘内任意两点的连线段仍在圆盘内：

整条线段在圆盘内 $\Longleftrightarrow$ 线段两端点都在圆盘内

这一步把「覆盖一条边」降级为「包住它的两个端点」，几何复杂度直接塌一档。

Step 2：从覆盖边到覆盖点—— $\binom{k}{2}$ 平台结构

承接上一步。如果圆盘里有 $k$ 个原始点，这 $k$ 个点两两之间共 $\binom{k}{2}$ 条边、其两端点都在圆内 $\Rightarrow$ 这 $\binom{k}{2}$ 条边上的丘丘人全保证被秒。

所以题目等价为：

对每个 $k = 2, 3, \dots, n$ ，求「至少包住 $k$ 个原始点的最小圆」的半径 $\mathrm{ans}_k[k]$ 。

输出时，给定 $m$ 找最小的 $k_m$ 满足 $\binom{k_m}{2} \ge m$ ，那个槽的最小半径就是答案。代码里更优雅的写法：把每个候选圆按 $\binom{\text{in\_cir\_cnt}}{2}$ 直接落到 mn_rad[ans] 槽，最后做一遍 suffix-min 把「更大 $m$ 的最优半径」向左 propagate 到小 $m$ 上——殊途同归，省一步反查。

样例的 4 个圆刚好对应 $k = 2, 3, 4, 5$ 四个平台：

| $k$ | 圆 | 半径 ( $\mathrm{ans}_k[k]$ ) | 管的 $m$ |

| — | — | — | — |

| 2 | 紫（最近对直径） | 2.236 | 1 |

| 3 | 红（3 点外接） | 4.286 | 2, 3 |

| 4 | 蓝（4 点 MEC） | 7.382 | 4, 5, 6 |

| 5 | 绿（全 5 点 MEC） | 9.301 | 7, 8, 9, 10 |

每个 $k$ 管 $\binom{k}{2} - \binom{k-1}{2} = k - 1$ 个 $m$ ，正是三角形数 1, 2, 3, 4, ……

Step 3：MEC 定理迁移——候选圆只有 $O(n^3)$ 个

MEC（minimum enclosing circle）的关键结构性事实：

MEC 定理： $n$ 个点的 MEC ，边界圆周上恰好经过 2 或 3 个原始点。

这是 Welzl 随机增量算法的依据。

• 「至少 2」：反证。如果边界上 0 或 1 个原始点，可以把圆心稍微挪一挪 $+$ 半径稍减，所有包含点继续在内 $\Rightarrow$ 半径更小，矛盾。

• 「至多 3」：平面上不共线 3 点决定唯一外接圆，题面保证「无三点共线」就是为了避开退化。

关键迁移：本题最优圆 $R^*$ （最小 $k$ 点覆盖圆）也满足这条结构性质——同样的 shrink/move 论证：若 $R^*$ 边界 $b \le 1$ 个原始点，可以缩小并保持「含 $\ge k$ 个点」不变 $\Rightarrow$ 与最优矛盾。所以 $R^*$ 必定是某个 $|S| \ge k$ 的子集的 MEC，由 2 或 3 个原始点决定。

这一刀把「枚举对象」从点的子集翻转成了圆。

候选圆集合：

• $\binom{n}{2}$ 个 两点直径圆（任选两点作直径）

• $\binom{n}{3}$ 个 三点外接圆（任选三点的 circumcircle）

规模 $O(n^3)$ ，对每个圆 $O(n)$ 数它包了多少个原始点 $\to$ 总 $O(n^4)$ 。

Step 4：复杂度算账

$n = 100$ 时：

$$\binom{100}{2} + \binom{100}{3} = 4\,950 + 161\,700 \approx 1.67 \times 10^5 \text{ 候选圆}$$

每圆 $\times 100$ 次数点 $\to$ 约 $1.67 \times 10^7$ 次基本运算。2 秒时限内相当宽松，连卡常都不需要。

Step 5：FP 精度坑——这题的 WA 点

枚举候选圆时，圆的 2 或 3 个定义点本应在边界上（数学上 $|p - c|^2 = r^2$ 恰好相等）。但 circle_from_diameter / outcircle_triangle 算出来的 r = sqrt(d) / 2 后，squared(r) = r * r 经过 sqrt 一来再 square 一回的 round trip，得到的不再是精确的 $d/4$ ，会有 ULP 级误差：

d  =  5: r*r = 1.2500000000000002,  d/4 = 1.25
d  = 13: r*r = 3.2499999999999996,  d/4 = 3.25   ← r*r < d/4，边界被判到圆外
d  = 20: r*r = 5.000000000000001,   d/4 = 5.0
d  = 50: r*r = 12.500000000000002,  d/4 = 12.5
d  =113: r*r = 28.250000000000004,  d/4 = 28.25

如果用 dist² <= r² 严格比较，当 r² 偶尔比真值小时，定义点被判到圆外（dist² > r²），漏算 $\to$ in_cir_cnt 不对 $\to$ mn_rad[m] 拿不到本该的候选半径 $\to$ WA。

样例 $d = 20$ 那个紫圆恰好走在 $+\varepsilon$ 一侧（<= 成立、定义点被算入），样例侥幸过；但测试数据里只要撞一个 $d = 13$ 这类形状，定义这个 diameter circle 的 2 个原点就漏算，整个候选圆失效。

修法：用 sgn(dist² - r²) <= 0 容差判定。

// AC https://vjudge.net/solution/69993234 使用 sgn 避免精度问题
template<class U>
bool is_point_in_circle(const Point<U> &p) {
    return sgn(distancePPNorm(p, c) - squared(r)) <= 0;
}

sgn 把 $|x| < \varepsilon$ 当作 0，吸收 sqrt $\to$ square 的 ULP 抖动。这个 patch 顺手同步到了 ICPC 几何模板 + espanso :Circle snippet，以后展开就自带正确版。

📎 动画与源码

完整带教对话录 PDF（mentor.tex 编译产物，含 6 步推导 + 我画的 4 个圆草图 + 全过程问答）在末尾附件区，可下载查看。

AC 代码

AC 提交链接（vjudge / Gym-105231I）

核心 Solve() 函数：枚举 $\binom{n}{3}$ 个外接圆 + $\binom{n}{2}$ 个直径圆，每个圆 $O(n)$ 数包含点数，按 $\binom{\text{in\_cir\_cnt}}{2}$ 落到 mn_rad 槽，最后 suffix-min 把大 $m$ 的最优半径向左 propagate。

心路历程（WA → AC）

• 第一次提交：大数据 WA，样例 AC。算法骨架完全对，suffix-min 也对，输入输出格式也对。

• 卡点诊断思路：「样例 AC + 大数据 WA + 几何题」三联立基本就是 FP 精度在 boundary 上吞 byte。

• 定位到 is_point_in_circle 的 dist² <= r² 严格比较——r = sqrt(d)/2 再 squared(r) 跑了一趟 sqrt → square 的 round trip，对 ll 整数输入精度只够覆盖大约半数 $d$ 值。

• 样例 $d = 20$ 那个紫圆（直径 $(-6,-9) \leftrightarrow (-4,-5)$ ）正好走在 $+\varepsilon$ 一侧，所以样例没暴露这个 bug；测试数据撞 $d = 13$ 类形状才漏算。

• 修法：return sgn(distancePPNorm(p, c) - squared(r)) <= 0; 把硬比较改成 sgn 容差判定，一行改完 AC。

• 顺便把这个 patch 同步到 ICPC 几何模板 的 Circle struct + espanso :Circle snippet，以后再做几何题展开模板就自带正确版，省一次踩同一个坑。

附件

完整带教对话录（mentor.tex 编译产物 PDF，含 6 步推导）+ AC C++ 源码（.cpp.txt）直接附在下方，可下载查看。

展开完整源码

// teamname: Gospel_rock
/**
 * Problem: Neuvillette Circling
 * Contest: Gym
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/Gym-105231I#author=translator:1281309:zh
 * Created: 2026-05-20 00:51:32
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define fsp(x) fixed<<setprecision(x)

using namespace std;

#if 1 && defined(LOCAL)
// @formatter:off
namespace DBG {
	template<typename T> void debug(T x);
	void debug(bool x);
	void debug(string x);
	template<typename T> void debug(vector<T> v);
	template<typename T, size_t N> void debug(array<T, N> v);
	template<typename T> void debug(set<T> s);
	template<typename T, typename U> void debug(pair<T, U> p);
	template<typename T, typename U> void debug(map<T, U> m);
	template<typename, typename = void> constexpr bool _has_iter_v = false;
	template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
	template<typename T>
	void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
	template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
	template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
	template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
	template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
	template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
	void _dbg() { cerr << endl; }
	template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
// @formatter:on
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr<<"\n---------------------------------------------------\n"
#define cEnd cerr<<"\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 * 2026-2-3  增加编译器识别 Real 类型功能
 * 2026-3-19 增加了从斜率式和一般式构造 Line
 * 2026-5-4  几何模板大改（QOJ 784 沉淀）：新增 isqrt / sqrtL、cross 三参数重载、polygonSignedArea，reorder_polygon 整体判向，isConvex 加 strict 参数，新增凸多边形直径旋转卡壳
 * 2026-5-5  Luogu P16223 沉淀：Point 加 id 字段，convex_diameter 加 n <= 2 退化特判，新增 furthest_pair_of_point
 * 2026-5-6  P3187 沉淀：getintersect 加浮点 assert + 显式 (DB) cross，make_convex_hull 加 strict 参数，新增 minimum_rectangle_cover
 * 2026-5-11 几何全面模板化：Point / Line 改 template<class T>，T 自动分流 ll / i128 / DB
 * 2026-5-12 加入了 Circle 类
 * 2026-5-13 加入了 half_plane_cut 和 unique_line_polar_angle_sort，加入了隐式转换和转换方向
 * 2026-5-15 加入了 HullMode
 */

// floor(sqrt(n)), n >= 0；二分 + 防溢出
i128 isqrt(i128 n) {
	if (n <= 0) return 0;
	i128 lo = 0, hi = (i128)2e18; // sqrt(4e36) <= 2e18
	while (lo < hi) {
		i128 mid = lo + (hi - lo + 1) / 2;
		if (mid <= n / mid) lo = mid; // 等价 mid*mid <= n，避免 i128 平方溢出
		else hi = mid - 1;
	}
	return lo;
}

// 统一 sqrt 入口：浮点直接 sqrtl；整数（含 i128）走 isqrt + fraction，避免 (long double) i128 在 n > 2^53 时丢整数精度。
template<typename T>
long double sqrtL(T n) {
	if constexpr (is_floating_point_v<T>) {
		return sqrtl((long double)n);
	} else {
		i128 ni = (i128)n;
		if (ni <= 0) return 0;
		i128 i = isqrt(ni);
		long double id = (long double)i;
		long double rd = (long double)(ni - i * i);
		// sqrt(i^2 + r) = i * sqrt(1 + r/i^2)
		return id * sqrtl(1.0L + rd / (id * id));
	}
}

// x*x 安全平方: 整数升 i128 防溢出 (1000^2 不会溢, 但模板要扛 1e9 量级输入),
// 浮点原样 T*T 不动 (i128 没浮点意义).
template<class T>
auto squared(T x) {
	if constexpr (is_floating_point_v<T>) {
		return x * x;
	} else {
		return (i128)x * (i128)x;
	}
}

template<class T>
int sgn(T x) {
	if (-eps < x && x < eps) return 0;
	return x < 0 ? -1 : 1;
}

template<class T>
struct Point {
	T x, y;
	int id = -1; // 原始下标. -1 表示派生点 (+ - * 等算术结果) 或未赋值, id 无意义

	explicit Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {
	}

	// Point<U> -> Point<T> 隐式 (common_type 单调升档方向, U -> T 必须无损):
	// common_type_t<U, T> == T 才放行 (例 ll -> DB 通; DB -> ll 拦, 防 truncation)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	Point(const Point<U> &o) : x((T)o.x), y((T)o.y), id(o.id) {
	}

	// 只对左值生效的复合运算符
	Point &operator+=(Point p) & {
		x += p.x, y += p.y;
		return *this;
	}

	Point &operator-=(Point p) & {
		x -= p.x, y -= p.y;
		return *this;
	}

	Point &operator*=(T t) & {
		x *= t, y *= t;
		return *this;
	}

	Point &operator/=(T t) & {
		x /= t, y /= t;
		return *this;
	}

	Point operator-() const { return Point(-x, -y); }

	friend Point operator+(Point a, Point b) { return a += b; }
	friend Point operator-(Point a, Point b) { return a -= b; }

	// 标量乘除: 返回 Point<common_type_t<T, U>> (C++14), 自动算公共类型
	// <ll,ll>=ll / <ll,DB>=DB / <DB,ll>=DB; R==T 走 copy ctor, R!=T 走 converting ctor
	template<class U>
	friend auto operator*(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r *= b;
		return r;
	}

	template<class U>
	friend auto operator*(U a, Point b) {
		Point<common_type_t<T, U> > r = b;
		r *= a;
		return r;
	}

	template<class U>
	friend auto operator/(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r /= b;
		return r;
	}

	friend bool operator<(Point a, Point b) {
		int sx = sgn(a.x - b.x);
		if (sx != 0) return a.x < b.x;
		return a.y < b.y;
	}

	friend bool operator>(Point a, Point b) { return b < a; }

	friend bool operator==(Point a, Point b) {
		return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
	}

	friend bool operator!=(Point a, Point b) { return !(a == b); }

	friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
	friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }

	auto norm() const {
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t)x * x + (__int128_t)y * y;
		} else {
			return x * x + y * y;
		}
	}

	DB abs() const { return sqrtL(norm()); }

	Point rot90() const {
		return Point(-y, x);
	}

	Point<DB> rot(DB ang) const {
		return Point<DB>(cosl(ang) * x - sinl(ang) * y, sinl(ang) * x + cosl(ang) * y);
	}

	// L1 范数 (曼哈顿) = |x| + |y|. 整型分支走 __int128_t 防溢出.
	auto normL1() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t)ax + (__int128_t)ay;
		} else {
			return ax + ay;
		}
	}

	// Linf 范数 (切比雪夫) = max(|x|, |y|). 返回类型与 T 同.
	T normLinf() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		return ax > ay ? ax : ay;
	}
};

template<class T, class U>
auto cross(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	//（改为这个非float，那么在类型为I128时，仍然可以计算）
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
	} else {
		return a.x * b.y - a.y * b.x;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) × (b - o)
// 用途: 判 3 点 turn (>0 左转, <0 右转, =0 共线) / 2 倍三角形有向面积 / 凸包面积扫描
template<class T, class U, class V>
auto cross(Point<T> o, Point<U> a, Point<V> b) {
	return cross(a - o, b - o);
}

template<class T, class U>
auto dot(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t)a.x * b.x + (__int128_t)a.y * b.y;
	} else {
		return a.x * b.x + a.y * b.y;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) · (b - o)
// 用途: 判夹角钝/直/锐 (>0 锐, =0 直, <0 钝) / 投影长度的有符号 2 倍 / 点在线段上的位置判定
template<class T, class U, class V>
auto dot(Point<T> o, Point<U> a, Point<V> b) {
	return dot(a - o, b - o);
}

// 采用两点式
template<class T>
struct Line {
	Point<T> p1, p2;

	Line() = default;

	Line(Point<T> a, Point<T> b) : p1(a), p2(b) {
	}

	// Line<U> -> Line<T> 隐式 (common_type 单调升档方向, 同 Point converting ctor)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	Line(const Line<U> &o) : p1(o.p1), p2(o.p2) {
	}

	// AC https://qoj.ac/submission/2146870
	Line(T k, T c) : p1(Point<T>(0, c)), p2(Point<T>(1, k + c)) {
	}

	friend bool operator<(Line a, Line b) {
		if (a.p1 != b.p1) return a.p1 < b.p1;
		return a.p2 < b.p2;
	}

	friend bool operator==(Line a, Line b) {
		if (a.p1 != b.p1) return false;
		if (a.p2 != b.p2) return false;
		return true;
	}

	friend istream &operator>>(istream &is, Line &e) {
		T a, b, c, d;
		is >> a >> b >> c >> d;
		e = Line(Point<T>(a, b), Point<T>(c, d));
		return is;
	}

	friend ostream &operator<<(ostream &os, Line l) {
		return os << "<" << l.p1 << ", " << l.p2 << ">";
	}
};

Line<DB> gen_line_from_general(DB a, DB b, DB c) {
	// 方向向量 (b, -a)
	Point<DB> p1, p2;
	if (b != 0) {
		p1 = Point<DB>(0, -c / b);
	} else {
		p1 = Point<DB>(-c / a, 0);
	}
	p2 = Point<DB>(p1.x + b, p1.y - a);
	return Line<DB>(p1, p2);
}

// 使用这个东西，Point 必须是 double 等浮点类型
template<class T, class U>
Point<DB> project(Point<T> p, Line<U> l) {
	Point<DB> vec = l.p2 - l.p1;
	//                        这个距离反正早除晚除都要除掉
	DB r = dot(vec, p - l.p1) / ((DB)vec.x * vec.x + vec.y * vec.y);
	return l.p1 + vec * r;
}

template<class T, class U>
Point<T> reflect(Point<T> p, Line<U> l) {
	Point<T> proj = project(p, l);
	return proj + proj - p;
}

mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

constexpr int ON_SEGMENT = 0;
constexpr int COUNTER_CLOCKWISE = 1;
constexpr int CLOCKWISE = -1;
constexpr int ONLINE_BACK = 2;
constexpr int ONLINE_FRONT = -2;

template<class T, class U>
int CCW(Point<T> p, Line<U> l) {
	Point<DB> a = l.p2 - l.p1;
	Point<DB> b = p - l.p1;
	if (sgn(cross(a, b)) > 0) {
		return COUNTER_CLOCKWISE;
	}
	if (sgn(cross(a, b)) < 0) {
		return CLOCKWISE;
	}
	if (sgn(dot(a, b)) < 0) {
		return ONLINE_BACK;
	}
	if (a.norm() < b.norm()) return ONLINE_FRONT;
	return ON_SEGMENT;
}

template<class T, class U>
bool isOrthogonal(Line<T> a, Line<U> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(dot(c, d));
}

template<class T, class U>
bool isParallel(Line<T> a, Line<U> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(cross(c, d));
}

template<class T, class U>
bool isSegIntersect(Line<T> a, Line<U> b) {
	// 判断线段相交
	return CCW(b.p1, a) * CCW(b.p2, a) <= 0 && CCW(a.p1, b) * CCW(a.p2, b) <= 0;
}

// bool isIntersectStrict(Line a,Line b){    // 判断线段相交
//     return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0     (利用叉乘乘以自身为0，消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式  拿到的是两直线交点
template<class T, class U>
Point<DB> getintersect(const Line<T> &a, const Line<U> &b) {
	Point<DB> p = a.p1, v = a.p2 - a.p1, q = b.p1, w = b.p2 - b.p1;
	Point<DB> u = p - q;
	DB t = (DB)cross(w, u) / cross(v, w);
	return p + v * t;
}

// 距离平方（不开方）：旋转卡壳里 ans 反复更新，留到最后一次 sqrt
template<class T, class U>
auto distancePPNorm(const Point<T> &a, const Point<U> &b) {
	return (a - b).norm();
}

// L2 欧几里得距离 (sqrt 版, 用 long double). 整型坐标走 isqrt + fraction 不丢精度.
template<class T, class U>
DB distancePP(const Point<T> &a, const Point<U> &b) {
	return (a - b).abs();
}

// L1 曼哈顿距离 = |dx| + |dy|. 返回类型继承 normL1 (整型 -> __int128_t, 浮点 -> T).
template<class T, class U>
auto distancePPL1(const Point<T> &a, const Point<U> &b) {
	return (a - b).normL1();
}

// Linf 切比雪夫距离 = max(|dx|, |dy|). 返回类型 T.
template<class T, class U>
T distancePPLinf(const Point<T> &a, const Point<U> &b) {
	return (a - b).normLinf();
}

// 也可以用 project 来算
template<class T, class U>
DB distancePL(Point<T> p, Line<U> l) {
	auto val = cross(l.p1, l.p2, p);
	return sgn(val) * val / (l.p2 - l.p1).abs();
}

// AC https://qoj.ac/submission/2001668
template<class T, class U>
DB distancePS(Point<T> p, Line<U> l) {
	// 避免 distanceSS 调用的时候发生这个退化（即线段退化为了点）
	if (l.p1 == l.p2) {
		return (p - l.p1).abs();
	}
	auto t = l.p2 - l.p1;
	if (sgn(dot(t, p - l.p1)) < 0) {
		return (p - l.p1).abs();
	}
	if (sgn(dot(t, p - l.p2)) > 0) {
		return (p - l.p2).abs();
	}
	return distancePL(p, l);
}

// AC https://qoj.ac/submission/2001588
template<class T, class U>
DB distanceSS(Line<T> a, Line<U> b) {
	if (isIntersect(a, b)) return 0;
	return min({distancePS(a.p1, b), distancePS(a.p2, b), distancePS(b.p1, a), distancePS(b.p2, a)});
}

// ===== 圆 (Circle) =====

// 圆弧 from -> to 的逆时针弧角差 [0, 2pi), 不是 abs(to - from)
static DB ccw_angle(DB theta_from, DB theta_to) {
	DB d = std::fmod(theta_to - theta_from, 2 * PI);
	if (d < 0) d += 2 * PI;
	return d;
}

enum CircleRelation {
	// 表示这个公切线个数; COINCIDENT (-1) 是重合 sentinel (无穷多公切线)
	COINCIDENT = -1,
	ONE_CONTAINS_OTHER = 0,
	INTERNALLY_TANGENT = 1,
	INTERSECTING = 2,
	EXTERNALLY_TANGENT = 3,
	EXTERNALLY_APART = 4,
};

template<class T>
struct Circle {
	Point<T> c;
	T r;

	Circle() = default;

	Circle(Point<T> c_, T r_) : c(c_), r(r_) {
	}

	// 圆上极角 theta 处的点: c + (r cos theta, r sin theta)
	// theta 不限定范围 (允许负值 / > 2pi), 始终走 cos/sin 不抛 assert
	Point<DB> point_at(DB theta) const {
		return Point<DB>((DB)c.x + (DB)r * cosl(theta),
		                 (DB)c.y + (DB)r * sinl(theta));
	}

	void check_theta(DB theta) const {
#ifdef LOCAL
		assert(theta >= -eps && theta <= 2 * PI + eps);
#endif
		(void)theta;
	}

	DB arc_length(DB theta) const {
		check_theta(theta);
		return (DB)r * theta;
	}

	DB chord_length(DB theta) const {
		check_theta(theta);
		return 2.0L * (DB)r * sinl(theta / 2);
	}

	// 弓形高 (sagitta) = r (1 - cos(theta / 2))
	DB sagitta(DB theta) const {
		check_theta(theta);
		return (DB)r * (1.0L - cosl(theta / 2));
	}

	// 扇形面积 = (1/2) r^2 theta
	DB sector_area(DB theta) const {
		check_theta(theta);
		return 0.5L * (DB)r * r * theta;
	}

	// 弓形面积 = (1/2) r^2 (theta - sin theta)
	// AC https://vjudge.net/solution/69814399 (Area of the Devil)
	DB segment_area(DB theta) const {
		check_theta(theta);
		return 0.5L * (DB)r * r * (theta - sinl(theta));
	}

	// AC https://vjudge.net/solution/69993234 使用 sgn 避免精度问题
	template<class U>
	bool is_point_in_circle(const Point<U> &p) {
		return sgn(distancePPNorm(p, c) - squared(r)) <= 0;
	}

	friend istream &operator>>(istream &is, Circle &c) {
		is >> c.c >> c.r;
		return is;
	}

	// 用于 debug
	friend ostream &operator<<(ostream &os, Circle &c) {
		os << "<" << c.c << "," << c.r << ">";
		return os;
	}
};

// 两点为直径的圆: 圆心为两点中点, 半径为两点距离的一半
// 退化 (两点重合): 半径为 0, 圆心即该点 (退化为点, 是合法结果, 非 sentinel)
Circle<DB> circle_from_diameter(Point<DB> a, Point<DB> b) {
	return Circle<DB>((a + b) / 2, distancePP(a, b) / 2);
}

// === incircle_triangle + outcircle_triangle (espanso :incircleOutcircle, 拆自 :Circle)
//     依赖: :Point + :Circle
// 三角形内接圆: 圆心为加权重心 (权 = 对边长), 半径 = min(圆心到三边距离)
// 退化 (共线 / 任意两点重合, cross == 0): 内接圆不存在, 返回 r=0 sentinel (圆心位置无意义)
// AC https://vjudge.net/solution/69920478 (CGL_7_B)
Circle<DB> incircle_triangle(Point<DB> a, Point<DB> b, Point<DB> c) {
	if (sgn(cross(a, b, c)) == 0) return Circle<DB>(a, 0);
	DB ab = distancePP(a, b), ac = distancePP(a, c), bc = distancePP(b, c);
	Point<DB> I = (a * bc + ac * b + ab * c) / (ab + ac + bc);
	return Circle<DB>(I, min({distancePS(I, Line(a, c)), distancePS(I, Line(a, b)), distancePS(I, Line(b, c))}));
}

// 三角形外接圆: 圆心是两条边的垂直平分线交点
// 退化 (共线 / 任意两点重合, cross == 0): 外接圆不存在, 改返回覆盖三点的最小圆 (以最远点对为直径)
// AC https://vjudge.net/solution/69927652 (CGL_7_C)
Circle<DB> outcircle_triangle(Point<DB> a, Point<DB> b, Point<DB> c) {
	if (sgn(cross(a, b, c)) == 0) {
		DB ab = distancePP(a, b), ac = distancePP(a, c), bc = distancePP(b, c);
		if (ab >= ac && ab >= bc) return circle_from_diameter(a, b);
		if (ac >= bc) return circle_from_diameter(a, c);
		return circle_from_diameter(b, c);
	}
	Point<DB> abMid = (a + b) / 2, acMid = (a + c) / 2;
	Point<DB> vecAb = (b - a).rot90(), vecAc = (c - a).rot90();
	Point<DB> I = getintersect(Line(abMid, abMid + vecAb), Line(acMid, acMid + vecAc));
	return Circle<DB>(I, distancePP(I, a));
}


void Solve() {
	ll N;
	cin >> N;
	vector<Point<ll> > A(N);
	for (auto &p: A) {
		cin >> p;
	}
	vector<DB> mn_rad((N * (N - 1)) / 2 + 2,INFINITY);
	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j) {
			for (int k = j + 1; k < N; ++k) {
				auto [a,b,c] = make_tuple(A[i], A[j], A[k]);
				Circle<DB> c0 = outcircle_triangle(a, b, c);
				ll in_cir_cnt = 0;
				for (const auto &p: A) {
					if (c0.is_point_in_circle(p)) {
						in_cir_cnt++;
					}
				}
				ll ans = in_cir_cnt * (in_cir_cnt - 1) / 2;
				mn_rad[ans] = min(mn_rad[ans], c0.r);
			}
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j) {
			auto [a,b] = make_tuple(A[i], A[j]);
			Circle<DB> c0 = circle_from_diameter(a, b);
			ll in_cir_cnt = 0;
			for (const auto &p: A) {
				if (c0.is_point_in_circle(p)) {
					in_cir_cnt++;
				}
			}
			ll ans = in_cir_cnt * (in_cir_cnt - 1) / 2;
			mn_rad[ans] = min(mn_rad[ans], c0.r);
		}
	}
	for (int i = SZ(mn_rad) - 2; i >= 0; --i) {
		mn_rad[i] = min(mn_rad[i + 1], mn_rad[i]);
	}
	cout << fsp(8);
	for (int i = 1; i <= (N * (N - 1)) / 2; ++i) {
		cout << mn_rad[i] << "\n";
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase = 1; testcase <= lT; ++testcase)
	Solve();
	return 0;
}

/*
AC
https://vjudge.net/solution/69993234

*/

完整带教对话录（mentor.tex 编译产物，6 步推导 + 第 1 步用户手画 4 个圆草图 + 全过程问答 + WA 诊断）

Neuvillette_Circling.cpp.txt