洛谷 P1742 - 最小圆覆盖

题目大意

洛谷 P1742 最小圆覆盖：给 $N$ 个平面点（$N\le 10^5$，坐标实数），求一个半径最小、且能把所有点都包住（含边界）的圆，第一行输出半径、第二行输出圆心坐标，精度 $10^{-9}$。

样例

6 个点 (8,9) (4,7.5) (1,2) (5.1,8.7) (9,2) (4.5,1) → 半径 5、圆心 (5,5)。这个圆恰由 (8,9)、(1,2)、(9,2) 三点的外接圆决定，其余 3 点严格在内部——暗示了最小圆由至多 3 个边界点钉死。

思路讲解

一句话

随机增量法（Welzl）：当前圈外的点必落在新圈边界上，于是逐点加入、三层钉点维护当前最小圆，期望 $O(N)$。这道题真正的坑不在算法本身，在内层 for j / for k 必须升序——内层判定下标改对了、循环方向写反，照样直接 WA。

Welzl 灵魂：引理 + 自由度 + 前缀不变量

内核一句话：圈外点 ⇒ 必在新最小圆边界上（圆内部容不下它、又必须刚好罩住它）。每钉一个边界点，圆的自由度 $-1$：3 自由度 → 钉 $p_i$ 剩 2 → 钉 $p_j$ 剩 1（圆心锁在中垂线上）→ 钉 $p_k$ 剩 0（三点外接圆唯一）。

**关键不变量：**每层 $res$ = 「覆盖前缀 $p_0\dots p_{t-1}$ + 已钉点」的最小圆。正确性全靠它。

三层：L0 钉 0 点扫 $i$；L1 钉 $p_i$ 扫 $j$；L2 钉 $p_i,p_j$ 扫 $k$，谁在圈外就 res = 外接圆。随机打乱只把复杂度降到期望 $O(N)$，与正确性无关。

三层结构（核心循环，升序版）

template<class T>
Circle<DB> min_circle_cover(vector<Point<T> > A) {
	// 先打乱
	shuffle(all(A), rng);
	Circle<DB> res(A[0], 0);
	for (int i = 1; i < SZ(A); ++i) {
		if (!res.is_point_in_circle(A[i])) {
			res = Circle<DB>(A[i], 0);
			// 注意，我们的这个后缀点之前已经考虑过了，实际上我们是要覆盖前缀点
			for (int j = 0; j < i; ++j) {
				if (!res.is_point_in_circle(A[j])) {
					res = circle_from_diameter(A[i], A[j]);
					for (int k = 0; k < j; ++k) {
						if (!res.is_point_in_circle(A[k])) {
							res = outcircle_triangle(A[i], A[j], A[k]);
						}
					}
				}
			}
		}
	}
	return res;

⚠️ 内层必须升序，倒序为什么 WA（本题关键）

升序让「已扫过的点」恒等于引理担保仍在圈内的「前缀」$\{p_0\dots p_{j-1}\}$，两集合重合、归纳一步步闭合。

倒序时（for(j=i-1;j>=0;--j)）：在某个 $j$ 处重建圆，引理只担保覆盖前缀 $p_0\dots p_{j-1}$；但你实际已扫过的是后缀 $p_{j+1}\dots p_{i-1}$（大下标先遍历）。这批后缀点没人保证还在新圈里，而 $j$ 只减不回头、永不复查 → 被甩出就永久丢失。

• **同样例 6 点实测：**升序连跑 30/30 全 = $r{=}5$、圆心 (5,5)。

• 倒序飘忽：$r{=}5$（对） / $r{=}6.23$ 圆心 (5,9.375)（盖住但非最小 = WA） / $r{=}3.876$ 圆心 (7.05,5.35)（连 (1,2) 都没盖 = 非法解）。

• **两种坏法：**漏点（已扫点被甩出 → 非法），或后续 circle_from_diameter 重置把圆撑大（非最小）。

🎬 Note: 交互式演示：下面 3 张关键帧出自 mc_order_demo.html（完整可交互版在末尾「附件」，可自己点 Step、切升/倒序、拖引理点、滑前缀/后缀滑条）。

📎 动画与源码

完整可交互 HTML 演示、AC 源码、完整带教对话录 PDF 都在页面末尾「附件」节，直接点开 / 下载。

AC 代码

AC 提交链接：vjudge.net/solution/69974356

展开完整 C++ 源码

// teamname: Gospel_rock
/**
 * Problem: P1742 最小圆覆盖
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P1742
 * Created: 2026-05-18 17:16:40
 * 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, enable_if_t<is_same_v<common_type_t<U, T>, T>, int> = 0>
	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>
Point<T> reflect(Point<T> p, Line<T> 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>
bool isOrthogonal(Line<T> a, Line<T> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(dot(c, d));
}

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

template<class T>
bool isSegIntersect(Line<T> a, Line<T> 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>
Point<DB> getintersect(const Line<T> &a, const Line<T> &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>
auto distancePPNorm(const Point<T> &a, const Point<T> &b) {
	return (a - b).norm();
}

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

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

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

// 也可以用 project 来算
template<class T>
DB distancePL(Point<T> p, Line<T> 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>
DB distancePS(Point<T> p, Line<T> 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>
DB distanceSS(Line<T> a, Line<T> 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));
	}

	template<class U>
	bool is_point_in_circle(const Point<U> &p) {
		return distancePPNorm(p, c) <= squared(r);
	}

	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));
}

// AC https://vjudge.net/solution/69974356 最小圆覆盖
template<class T>
Circle<DB> min_circle_cover(vector<Point<T> > A) {
	// 先打乱
	shuffle(all(A), rng);
	Circle<DB> res(A[0], 0);
	for (int i = 1; i < SZ(A); ++i) {
		if (!res.is_point_in_circle(A[i])) {
			res = Circle<DB>(A[i], 0);
			// 注意，我们的这个后缀点之前已经考虑过了，实际上我们是要覆盖前缀点
			for (int j = 0; j < i; ++j) {
				if (!res.is_point_in_circle(A[j])) {
					res = circle_from_diameter(A[i], A[j]);
					for (int k = 0; k < j; ++k) {
						if (!res.is_point_in_circle(A[k])) {
							res = outcircle_triangle(A[i], A[j], A[k]);
						}
					}
				}
			}
		}
	}
	return res;
}


void Solve() {
	ll N;
	cin >> N;
	vector<Point<DB> > A(N);
	for (auto &p: A) {
		cin >> p;
	}
	auto ansc = min_circle_cover(A);
	cout << fsp(12) << ansc.r << "\n" << ansc.c.x << " " << ansc.c.y;
}

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/69974356

*/

心路历程（WA → AC）

• **第一次：**内层判定误写成 A[i] 而非 A[j] / A[k]，res 退化成半径 0 的点圆，只要有点在外答案就全错。

• **改对下标后仍 WA：**内层循环写成了倒序 for(j=i-1;j>=0;--j) / for(k=j-1;k>=0;--k)。

• **现象飘忽：**同样例点不同 shuffle 跑出 r=5（对）、r=6.23（盖住但非最小=WA）、r=3.876（连 (1,2) 都没盖=非法），一开始以为是精度/eps 问题，其实是结构错。

• **根因：**倒序破坏「前缀不变量」——引理重建只担保前缀，倒序实际已扫的是后缀，被甩出的点 j 只减不回头、永不复查。

• **修复：**内层改升序 for(j=0;j<i;++j) / for(k=0;k<j;++k)，固定样例点序回归 30/30 稳定 r=5、圆心 (5,5)。

**教训：**随机增量法的正确性不靠随机（随机只管期望复杂度），靠「已扫集合恒为前缀」这条不变量；扫描方向本身是正确性的一部分，不是风格选择。

附件

本题相关产物（可直接点开 / 下载）：

mentor.tex.txt

P1742_mini_circle.cpp.txt